QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #620512 | #3998. The Profiteer | tanfuxuan | TL | 37ms | 7160kb | C++14 | 2.3kb | 2024-10-07 18:42:40 | 2024-10-07 18:42:41 |
Judging History
answer
#include<bits/stdc++.h>
const int N=2e5+10;
int v[N],a[N],b[N];
int n,k,E;
using ll=long long;
ll kE;
struct bagpack{
std::vector<int> f;
void insert(int v,int w){
for(int i=k;i>=w;i--) f[i]=std::max(f[i],f[i-w]+v);
}
ll sum(){
ll ret=0;
for(int i=0,fi=0;i<=k;i++){
fi=std::max(fi,f[i]);
ret+=fi;
}
return ret;
}
}global,cur;
int ans[N];
void solve(int l1,int l2,int r1,int r2){
if(l1>l2) return;
// printf("%d~%d %d~%d\n",l1,l2,r1,r2);
int l3=l1+l2>>1;cur=global;
for(int i=l1;i<l3;i++) cur.insert(v[i],a[i]);
for(int i=l3;i<std::max(l2,r1);i++) cur.insert(v[i],b[i]);
int left=std::max(l2,r1),right=r2;
while(left<right){//求最小的 r 与 l3 对应
int mid=left+right>>1;bagpack tmp=cur;
for(int i=left;i<=mid;i++) tmp.insert(v[i],b[i]);
for(int i=mid+1;i<=right;i++) tmp.insert(v[i],a[i]);
if(tmp.sum()<=kE){
for(int i=mid+1;i<=right;i++) cur.insert(v[i],a[i]);
right=mid;
}
else{
for(int i=left;i<=mid;i++) cur.insert(v[i],b[i]);
left=mid+1;
}
}
// printf("ans[%d]=%d\n",l3,left);
ans[l3]=left;
if(l1==l2) return;
bagpack tmp=global;
for(int i=l3;i<=std::min(r1-1,l2);i++) global.insert(v[i],b[i]);
for(int i=left;i<r2;i++) global.insert(v[i],a[i]);
solve(l1,l3-1,r1,left);
global=tmp;
for(int i=l1;i<=l3;i++) global.insert(v[i],a[i]);
for(int i=std::max(l2+1,r1);i<left;i++) global.insert(v[i],b[i]);
solve(l3+1,l2,left,r2);
}
int main(){
scanf("%d%d%d",&n,&k,&E);kE=1ll*k*E;
for(int i=1;i<=n;i++) scanf("%d%d%d",v+i,a+i,b+i);
cur.f.resize(k+1);cur.insert(v[n],b[n]);
for(int i=1;i<n;i++) cur.insert(v[i],a[i]);
int left=1,right=n;//判无解
if(cur.sum()<=kE)//全部有解
left=right=n+1;
cur.f.clear();cur.f.resize(k+1);
cur.insert(v[n],b[n]);
while(left<right){//得到无解的 l 的最小值
int mid=left+right>>1;
bagpack tmp=cur;
for(int i=left;i<mid;i++) tmp.insert(v[i],a[i]);
for(int i=mid;i<right;i++) tmp.insert(v[i],b[i]);
if(tmp.sum()>kE){//无解
for(int i=mid;i<right;i++) cur.insert(v[i],b[i]);
right=mid;
}
else{
for(int i=left;i<=mid;i++) cur.insert(v[i],a[i]);
left=mid+1;
}
}
global.f.resize(k+1);
std::fill(ans+1,ans+n+1,n+1);
solve(1,left-1,1,n);
ll prt=0;
for(int i=1;i<=n;i++) prt+=n-ans[i]+1;
printf("%lld",prt);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5812kb
input:
4 5 3 3 2 4 1 2 3 2 1 2 3 1 3
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
4 5 4 3 2 4 1 2 3 2 1 2 3 1 3
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
4 5 5 3 2 4 1 2 3 2 1 2 3 1 3
output:
7
result:
ok single line: '7'
Test #4:
score: 0
Accepted
time: 37ms
memory: 7160kb
input:
200000 50 23333 2620 5 21 8192 17 34 6713 38 46 6687 13 42 390 9 13 4192 7 37 7898 17 21 1471 16 45 3579 22 40 9628 8 23 7164 28 45 3669 14 31 5549 29 35 4670 30 39 5811 15 20 4162 18 29 7590 29 41 7786 23 35 383 9 40 5576 39 46 5586 4 9 1110 14 33 8568 4 6 8548 39 42 9133 10 42 6679 22 39 8353 33 3...
output:
0
result:
ok single line: '0'
Test #5:
score: -100
Time Limit Exceeded
input:
200000 50 233332 8019 18 20 3111 27 40 2015 16 47 6491 17 18 1224 30 38 428 23 34 7521 4 41 7252 6 33 4121 32 45 4230 18 35 1605 21 42 9489 17 25 3704 35 45 6202 8 22 6493 1 5 3041 14 46 4509 23 43 9646 11 48 5294 19 27 3562 19 40 9408 30 47 1751 21 29 4053 4 27 5596 32 49 8609 13 29 1686 4 31 3588 ...