AcWing 1262. 鱼塘钓鱼
原题链接
简单
作者:
chenjiaqiy
,
2024-03-11 11:56:25
,
所有人可见
,
阅读 18
// Problem: 鱼塘钓鱼
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1264/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
#include <bits/stdc++.h> //�ص������㰮�ҵĶ���
using namespace std;
#define endl '\n'
#define ll long long
#define ld long double
#define umap unordered_map
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define rep_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(), v.end()
#define alls(a) a + 1, a + 1 + n
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define c1 cout << -1 << endl
int _, n, k, m;
typedef pair<int, int> PII;
priority_queue<int> maxx;
priority_queue<int, vector<int>, greater<int> > minx;
const int N = 100 + 10, inf = 1e9;
const double eps = 1e-8;
const double pi = acos(-1);
const int mod = 1e9 + 7;
int a[N], d[N], T[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> d[i];
for (int i = 2; i <= n; i++) cin >> T[i], T[i] += T[i - 1];
int t;
cin >> t;
int ans = -1;
//枚举只在前k个鱼塘钓鱼
for (int k = 1; k <= n; k++) {
int t1 = t - T[k]; //减去到这几个鱼塘赶路的时间,即能钓鱼的时间
priority_queue<PII> q;
for (int i = 1; i <= k; i++) {
q.push({a[i], i});//前K个鱼塘初始点入堆
}
int res = 0;//当前这种情况能掉到的最大的鱼
while (q.size() && t1 > 0) {
auto h = q.top();
q.pop();
res += h.x;
t1--;//时间减少一分钟
h.x -= d[h.y];//该鱼塘数量减少对应值
if (h.x > 0) q.push({h.x, h.y});//如果还能钓,就继续入堆
}
ans = max(ans, res);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//cin >> _;
_ = 1;
while (_--) {
solve();
}
return 0;
}