QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#40895 | #3998. The Profiteer | The_Nobody | WA | 361ms | 20128kb | C++ | 2.9kb | 2022-07-27 10:13:01 | 2022-07-27 10:13:03 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define Il inline
#define mem(u,v) memset(u,v,sizeof(u))
#define rep(i,a,b) for(int i=(a),KKK##i=(b);i<=KKK##i;i++)
#define drep(i,a,b) for(int i=(a),KKK##i=(b);i>=KKK##i;i--)
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define writesp(x) write(x),putchar(' ')
#define writeln(x) write(x),puts("")
//#define getchar nc
inline char nc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
using namespace std;
Il ll read(){ll sum=0,f=0;char ch=getchar();for(;!isdigit(ch);ch=getchar())f|=(ch=='-');for(;isdigit(ch);ch=getchar())sum=((sum<<1)+(sum<<3)+(ch^48));return f?-sum:sum;}
void write(const ll x){if(x<0){putchar('-');write(-x);return;}if(x>9)write(x/10);putchar(x%10+'0');}
char getc(){char ch=getchar();while(!isalpha(ch))ch=getchar();return ch;}
#define N 20000200
ll n,k,E,ans[N],f[N],top,ha,a[N],b[N],v[N],ANS,T;
struct node{ll i,k,t;}s[N];
bool chk(){
ll sum=0;
rep(i,1,k)sum+=f[i];
// cout<<sum<<endl;
return sum<=k*E;
}
void fix(){
rep(i,1,T)printf(" ");
}
void add(ll c,ll v){
// fix();cout<<"ADD"<<c<<' '<<v<<endl;
top++;
drep(j,k,c)if(f[j]<f[j-c]+v)s[++ha]=(node){j,f[j],top},f[j]=f[j-c]+v;
// fix();rep(i,1,k)cout<<f[i]<<' ';puts("");
}
void re(){
while(s[ha].t==top){
f[s[ha].i]=s[ha].k;
ha--;
}
top--;
// fix();cout<<"DEL"<<endl;
// fix();rep(i,1,k)cout<<f[i]<<' ';puts("");
}
void solve(ll l,ll r,ll x,ll y){
if(l>r||x>y)return;
// cout<<"SOL"<<l<<' '<<r<<' '<<x<<' '<<y<<endl;
if(x==y){
rep(i,l,r)ans[i]=x;
// cout<<"DONE"<<l<<' '<<r<<' '<<x<<endl;
// rep(i,1,k)cout<<f[i]<<' ';puts("");
return;
}
ll mid=(l+r+1)>>1;
rep(i,mid,min(r,x-1))add(b[i],v[i]);
rep(i,l,mid-1)add(a[i],v[i]);
// fix();cout<<"> ERF"<<' '<<mid<<endl;
ll L=max(mid,x),R=y;
while(L<R){
ll MID=(L+R)>>1;
// cout<<"> "<<L<<' '<<R<<endl;
rep(i,L,MID)add(b[i],v[i]);
rep(i,MID+1,R)add(a[i],v[i]);
bool tmp=chk();
// fix();cout<<"> "<<MID<<' '<<tmp<<endl;
rep(i,L,R)re();
if(tmp){
rep(i,MID+1,R)add(a[i],v[i]);
R=MID;
}
else{
rep(i,L,MID)add(b[i],v[i]);
L=MID+1;
}
}
// fix();cout<<"> GET"<<mid<<' '<<L<<endl;
ans[mid]=L;
rep(i,1,y-max(x,mid))re();
// rep(i,1,min(r,x)-l+1)re();
rep(i,l,mid-1)re();
rep(i,L+1,y)add(a[i],v[i]);
T++;
solve(l,mid-1,x,L);
T--;
rep(i,1,y-L)re();
rep(i,mid,min(r,x-1))re();
rep(i,l,min(mid,L))add(a[i],v[i]);
// rep(i,l,min(mid,L))if(!T)cout<<"ADDA"<<i<<endl;
rep(i,max(r,L),y)add(b[i],v[i]);
// rep(i,max(r,x),y)if(!T)cout<<"ADDB"<<i<<endl;
T++;
solve(mid+1,r,L,y);
T--;
rep(i,l,min(mid,x))re();
rep(i,max(r,x),L)re();
}
int main(){
n=read(),k=read(),E=read();
rep(i,1,n)v[i]=read(),a[i]=read(),b[i]=read();
solve(1,n,1,n+1);
// rep(i,1,n)cout<<ans[i]<<" ";puts("");
rep(i,1,n)ANS+=n-ans[i]+1;
writeln(ANS);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 13708kb
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: 2ms
memory: 13952kb
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: 2ms
memory: 13812kb
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: 361ms
memory: 19908kb
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
Wrong Answer
time: 351ms
memory: 20128kb
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 ...
output:
13413289
result:
wrong answer 1st lines differ - expected: '17523021', found: '13413289'