QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #44588 | #4585. Greedy Knapsack | eyiigjkn | ML | 2ms | 3748kb | C++14 | 810b | 2022-08-19 14:49:42 | 2022-08-19 14:49:43 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int w[100010],v[100010];
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>> que;
vector<pair<ll,ll>> vec;
int main()
{
int n,maxw=0;
ll m;
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&w[i]),maxw=max(maxw,w[i]);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
ll L=max(m-maxw+1,1ll),R=m,ans=0;
for(int i=1;i<=n;i++)
{
while(!que.empty() && que.top().first>=w[i])
{
auto p=que.top();que.pop();
vec.emplace_back(w[i]-1,p.second);
vec.emplace_back(p.first-w[i],p.second+v[i]);
}
for(auto j:vec) que.push(j);
if(w[i]<=L) L-=w[i],R-=w[i],ans+=v[i];
else if(w[i]<=R) que.emplace(R-w[i],ans+v[i]),R=w[i]-1;
}
for(;!que.empty();que.pop()) ans=max(ans,que.top().second);
cout<<ans<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3540kb
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: 3536kb
input:
5 10000000000 10 1 2 3 4 30 2 15 7 11
output:
65
result:
ok single line: '65'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
5 20 4 9 5 1 3 203 175 131 218 304
output:
900
result:
ok single line: '900'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3748kb
input:
1 1 1 1
output:
1
result:
ok single line: '1'
Test #5:
score: -100
Memory Limit Exceeded
input:
100000 200000 100000 99998 99996 99994 99992 99990 99988 99986 99984 99982 99980 99978 99976 99974 99972 99970 99968 99966 99964 99962 99960 99958 99956 99954 99952 99950 99948 99946 99944 99942 99940 99938 99936 99934 99932 99930 99928 99926 99924 99922 99920 99918 99916 99914 99912 99910 99908 999...