Submission #783643

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783643	2023-07-15T07:11:04 Z	kshitij_sodani	Long Distance Coach (JOI17_coach)	C++14	71 / 100	2000 ms	16696 KB

coach

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'


llo it[200001];
llo dp[200001];
llo xx[200001];
llo pre[200001];
llo pre2[200001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo x,n,m,w,t;
	cin>>x>>n>>m>>w>>t;
	vector<pair<pair<llo,llo>,llo>> ss;
	llo ans=((x/t)+1)*w;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		ss.pb({{it[i]%t,-1},it[i]/t});
	}
	ss.pb({{x%t,-1},x/t});
	for(llo i=0;i<m;i++){
		llo aa,bb;
		cin>>aa>>bb;
		if((aa)<(x%t)){
			ans+=((x/t)*w)+w;
			xx[i]=(x/t);
		}
		else{
			ans+=(((x/t))*w);
			xx[i]=(x/t)-1;
		}
		ss.pb({{aa,xx[i]},bb});
	}
	//cout<<ans<<endl;
	sort(ss.begin(),ss.end());
	dp[0]=0;
	llo ma=0;
	/*for(auto j:ss){
		cout<<j.a.a<<":"<<j.a.b<<":"<<j.b<<endl;
	}*/
	pre[0]=0;
	pre2[0]=0;
	for(int i=0;i<ss.size();i++){
		pre[i+1]=pre[i];
		pre2[i+1]=pre2[i];
		if(ss[i].a.b>=0){
			pre[i+1]+=ss[i].b;
			pre[i+1]-=w*ss[i].a.b;
			pre2[i+1]=pre2[i]+1;
		}
	}
	for(llo i=0;i<ss.size();i++){
		dp[i+1]=dp[i];
		if(ss[i].a.b==-1){
			//llo su=0;
			for(llo j=i-1;j>=0;j--){
				/*if(ss[j].a.b>=0){
					su+=(w*(-ss[i].b+1));//-ss[j].b;
				}*/
				llo su=-w*pre2[j]*(-ss[i].b+1);
				//slope is -ss[i].b+1
				//number of type 0 in prefix
				dp[i+1]=max(dp[i+1],dp[j]+su+(-ss[i].b+1)*pre2[i+1]*w+pre[j]-pre[i+1]);
			}
		}
		ma=max(ma,dp[i+1]);
		//cout<<dp[i+1]<<",";
	}
	//cout<<endl;
	ans-=ma;
	cout<<ans<<endl;
	






	return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~
coach.cpp:58:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(llo i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct

Subtask #2
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	0 ms	340 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	0 ms	340 KB	Output is correct
35	Correct	0 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	0 ms	340 KB	Output is correct

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	0 ms	340 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	0 ms	340 KB	Output is correct
35	Correct	0 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	0 ms	340 KB	Output is correct
38	Correct	8 ms	596 KB	Output is correct
39	Correct	8 ms	668 KB	Output is correct
40	Correct	8 ms	596 KB	Output is correct
41	Correct	8 ms	664 KB	Output is correct
42	Correct	9 ms	676 KB	Output is correct
43	Correct	6 ms	640 KB	Output is correct
44	Correct	10 ms	628 KB	Output is correct
45	Correct	8 ms	596 KB	Output is correct
46	Correct	8 ms	664 KB	Output is correct
47	Correct	9 ms	664 KB	Output is correct
48	Correct	8 ms	596 KB	Output is correct
49	Correct	8 ms	656 KB	Output is correct
50	Correct	9 ms	596 KB	Output is correct
51	Correct	8 ms	676 KB	Output is correct

Subtask #4
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	0 ms	340 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	0 ms	340 KB	Output is correct
35	Correct	0 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	0 ms	340 KB	Output is correct
38	Correct	8 ms	596 KB	Output is correct
39	Correct	8 ms	668 KB	Output is correct
40	Correct	8 ms	596 KB	Output is correct
41	Correct	8 ms	664 KB	Output is correct
42	Correct	9 ms	676 KB	Output is correct
43	Correct	6 ms	640 KB	Output is correct
44	Correct	10 ms	628 KB	Output is correct
45	Correct	8 ms	596 KB	Output is correct
46	Correct	8 ms	664 KB	Output is correct
47	Correct	9 ms	664 KB	Output is correct
48	Correct	8 ms	596 KB	Output is correct
49	Correct	8 ms	656 KB	Output is correct
50	Correct	9 ms	596 KB	Output is correct
51	Correct	8 ms	676 KB	Output is correct
52	Execution timed out	2068 ms	16696 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

Submission #783643

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 30.0 / 30.0

Subtask #3 25.0 / 25.0

Subtask #4 0 / 29.0

Subtask #1
16.0 / 16.0

Subtask #2
30.0 / 30.0

Subtask #3
25.0 / 25.0

Subtask #4
0 / 29.0