Submission #220702

#	Time	Username	Problem	Language	Result	Execution time	Memory
220702		kshitij_sodani	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	16 ms	5504 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52