QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#40895#3998. The ProfiteerThe_NobodyWA 361ms20128kbC++2.9kb2022-07-27 10:13:012022-07-27 10:13:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-27 10:13:03]
  • 评测
  • 测评结果:WA
  • 用时:361ms
  • 内存:20128kb
  • [2022-07-27 10:13:01]
  • 提交

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'