oj.uz

Submission #220702

# Submission time Handle Problem Language Result Execution time Memory
220702 2020-04-08T12:37:55 Z kshitij_sodani Semiexpress (JOI17_semiexpress) C++17
100 / 100
 16 ms 5504 KB 
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>

#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>

#include <functional>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <numeric>
#include <random>
#include <ratio>
#include <sstream>
#include <utility>

#include <bitset>
#include <deque>
#include <queue>
#include <map>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <string>
#include <set>

using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,m,k;
	cin>>n>>m>>k;
	llo aa,bb,cc;
	cin>>aa>>bb>>cc;
	llo it[m];
	llo tt;
	cin>>tt;
	for(llo i=0;i<m;i++){
		cin>>it[i];
	}
	
	llo ans=0;
	vector<llo> ne[m];
	for(llo i=1;i<m;i++){
		llo co=tt;
		co-=(it[i-1]-1)*bb;
		if(co<=0){
			continue;
		}
		llo ind=it[i-1]+1;

		ans+=max(min((co)/aa,it[i]-it[i-1]-1),(llo)0);
		ind+=co/aa;
		llo co3=0;
	//	cout<<ans<<" "<<co<<endl;
		while(ind<it[i] and co3<k-m){
			co-=(ind-it[i-1])*cc;
			llo de;
			if(co<0){
				break;
			}
			de=co/aa;
			ne[i].pb(min(de+1,it[i]-ind));
	//		cout<<ne[i][ne[i].size()-1]<<",";
			llo co2=co;
			co+=(ind-it[i-1])*cc;

			ind+=co2/aa+1;
			co3+=1;
		}
	//	cout<<endl;
	}
	//cout<<ans<<endl;
	priority_queue<pair<llo,pair<llo,llo>>> ac;
	for(llo i=1;i<m;i++){
		if(ne[i].size()>0){
			ac.push({ne[i][0],{i,0}});
		//	cout<<ne[i][0]<<" "<<i<<" "<<0<<endl;
		}
	}
	for(llo i=0;i<k-m;i++){

		if(ac.size()==0){
			break;
		}
		pair<llo,pair<llo,llo>> xx=ac.top();
		ac.pop();
		ans+=xx.a;
		if(xx.b.b<ne[xx.b.a].size()-1){
			ac.push({ne[xx.b.a][xx.b.b+1],{xx.b.a,xx.b.b+1}});
	//		cout<<ne[xx.b.a][xx.b.b+1]<<" "<<xx.b.a<<" "<<xx.b.b+1<<endl;
		}
	}
//	cout<<ans<<endl;
	for(llo i=1;i<m;i++){
		if((it[i]-1)*bb<=tt){
			ans+=1;
		}
	}
	cout<<ans<<endl;

	
	return 0;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:102:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(xx.b.b<ne[xx.b.a].size()-1){
      ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 512 KB Output is correct
23 Correct 16 ms 5504 KB Output is correct
24 Correct 5 ms 512 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 512 KB Output is correct
28 Correct 5 ms 512 KB Output is correct
29 Correct 12 ms 4224 KB Output is correct
30 Correct 8 ms 1920 KB Output is correct