Submission #375875

#	Time	Username	Problem	Language	Result	Execution time	Memory
375875		astoria	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	2 ms	492 KiB

semiexpress

#include "bits/stdc++.h"
using namespace std;

#define int long long

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n,m,k,a,b,c,t; //a=local, b=express, c=semiexpress; t = total time
	cin>>n>>m>>k>>a>>b>>c>>t;
	int s[m+5];
	for(int i=0; i<m; i++){ cin>>s[i]; s[i]--;}
	
	int len[m],ben[m],tot[m]; //len: how many, ben: how many more
	memset(len,0,sizeof(len)); memset(ben,0,sizeof(ben));
	bool can[m]; memset(can,0,sizeof(can));
	for(int i=0; i<m-1; i++){
		tot[i] = (s[i+1]-s[i]-1); //total stations to reach
		int ttbef = b*s[i]; //time taken to reach here by express
		if(ttbef<=t) can[i]=1;
		if(!can[i]) continue;
		
		int rem = t - ttbef; //time remaining for local
		len[i] = rem/a; //max number of stations local can reach
		len[i] = min(len[i],tot[i]); //can't do more than tot
		
		int nxtpo = len[i]+1; //we want to take a semiexpress to this station
		int remaft = rem - (c*nxtpo); //semiexpress cost
		if(remaft<0) continue; //if remainder is too little then cannot
		ben[i] = (remaft/a)+1; //the station plus any after by local
		ben[i] = min(ben[i], tot[i]-len[i]); //can't do more than tot
	}
	
	if(b*s[m-1] <= t) can[m-1]=1;
	
	for(int ahc=0; ahc<(k-m); ahc++){
		int mxben=-1, mxpo=-1;
		for(int i=0; i<m-1; i++){
			if(ben[i]>mxben){ mxben=ben[i]; mxpo=i;}
		}
		if(mxben<=0) break;
		int i = mxpo;
		//we take mxben
		len[i] += ben[i];
		//calc ben again
		int nxtpo = len[i]+1;
		int remaft = t - (b*s[i]) - (c*nxtpo);
		if(remaft<0){ ben[i]=0; continue;} //remainder too little
		ben[i] = (remaft/a)+1;
		ben[i] = min(ben[i],tot[i]-len[i]); //can't do more than tot
	}
	int an=0;
	for(int i=0; i<m-1; i++){
		an+=len[i]; //cout<<len[i]<<' '; 
	}
	cout<<endl;
		
	for(int i=1; i<m; i++) an+=can[i];
	cout<<an;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52