Submission #854664

#	Time	Username	Problem	Language	Result	Execution time	Memory
854664		willychan	Semiexpress (JOI17_semiexpress)	C++14	48 / 100	1050 ms	464 KiB

semiexpress

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
#define int ll

ll dp[3005];

vector<int> stop;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m,k;cin>>n>>m>>k;
	int a,b,c;cin>>a>>b>>c;
	ll T;cin>>T;
	stop.resize(m);
	k-=m;
	for(int i=0;i<k;i++) dp[i]=0;
	for(int i=0;i<m;i++){cin>>stop[i];stop[i]--;}
	for(int i=0;i<m-1;i++){
		if(stop[i]*b>T) break;
		for(int g=k;g>=0;g--){
			int ss = stop[i];
			int tt = stop[i]*b;
			for(int j=0;j<=g;j++){
				ss = ss+((T-tt)/a)+1;
				dp[g] = max(dp[g-j]+min(ss-stop[i],stop[i+1]-stop[i]),dp[g]);
				tt = stop[i]*b+(ss-stop[i])*c;
				if(tt>T) break;
			}
		}
	}
	cout<<dp[k]+(((n-1)*b)<T)-1<<"\n";
	return 0;
}

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