Submission #1199430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199430		Saul0906	Semiexpress (JOI17_semiexpress)	C++20	48 / 100	150 ms	327680 KiB

semiexpress

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define mid ((l+r)>>1)
#define endl "\n"

using namespace std;

using vi = vector<int>;

const int N=305;

int dp[N][N][N]{};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n, m, k, a, b, c, t;
	cin>>n>>m>>k>>a>>b>>c>>t;
	vi p(m);
	bool ex[n+1]{};
	ll lst[n+1]{}, dis[n+1]{};
	rep(i,0,m) cin>>p[i], ex[p[i]]=true;
	rep(i,1,n+1){
		if(ex[i]) lst[i]=i;
		else lst[i]=lst[i-1];
		dis[i]=(lst[i]-1)*b+(i-lst[i])*c;
	}
	rep(i,0,n+1) rep(j,0,n+1) rep(k,0,n+1) dp[i][j][k]=-N;
	dp[0][0][0]=0;
	rep(i,1,n+1){ //iterate all stations
		rep(j,0,n+1){ //iterate the number of fixed stations
			rep(k,0,n+1){ //the last fixed station
				if(ex[i]){
					dp[i][j+1][i]=max(dp[i-1][j][k]+(dis[i]<=t),dp[i][j+1][i]);
				}else{
					dp[i][j+1][i]=max(dp[i-1][j][k]+(dis[i]<=t),dp[i][j+1][i]);
					dp[i][j][k]=max(dp[i-1][j][k]+(dis[k]+(i-k)*a<=t),dp[i][j][k]);
				}
			}
		}
	}
	int ans=0;
	rep(i,0,n+1) ans=max(ans,dp[n][k][i]);
	cout<<ans-1<<endl;
}

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