QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252624 | #4585. Greedy Knapsack | lam | WA | 0ms | 3704kb | C++14 | 1.5kb | 2023-11-15 22:49:39 | 2023-11-15 22:49:40 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int n;
int w[maxn], v[maxn];
map<int,int> res;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n; int T; cin >> T;
int mmax = -1;
for (int i=1; i<=n; i++) cin>>w[i], mmax = max(mmax, w[i]);
for (int i=1; i<=n; i++) cin>>v[i];
int L = max(T - mmax + 1, 0LL); int R = T;
int pivot = -1;
int ans = 0LL;
for (int i=1; i<=n; i++)
{
if (L < w[i])
{
pivot = i;
break;
}
L -= w[i]; R -= w[i];
ans += v[i];
}
if (pivot == -1)
{
cout << ans << '\n';
return 0;
}
int sum = 0;
for (int i = pivot; i <= n; i++)
{
int x = w[i] + L;
if (x > R) continue;
if (R - w[i] <= L + w[i] - 1) {
R = L + w[i] - 1;
for (int l = L, r = L + w[i]; r <= R; l++, r++) {
res[l] = max(res[l], res[r] + v[i]);
}
}
else {
sum += v[i];
for (int l = L, r = L + w[i]; l <= L + w[i] - 1; l++, r++) {
res[r] = max(res[r], res[l] - v[i]);
}
L += w[i];
}
}
int bruh = -1e18;
for (int i = L; i <= R; i++) bruh = max(bruh, res[i]);
bruh += ans + sum;
cout << bruh << '\n';
}
/**
5 10
10 1 2 3 4
1 1 1 1 1
**/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
input:
5 10 10 1 2 3 4 1 1 1 1 1
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
5 10000000000 10 1 2 3 4 30 2 15 7 11
output:
65
result:
ok single line: '65'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3704kb
input:
5 20 4 9 5 1 3 203 175 131 218 304
output:
421
result:
wrong answer 1st lines differ - expected: '900', found: '421'