Submission #220612

#	Time	Username	Problem	Language	Result	Execution time	Memory
220612		kshitij_sodani	Semiexpress (JOI17_semiexpress)	C++17	0 / 100	5 ms	384 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;
	llo pre[m][2];
	for(llo i=1;i<m;i++){
		llo tot=0;
		llo tot2=0;
		if((it[i]-1)*bb<=tt){
			ans+=1;
		}
		for(llo j=it[i-1];j<it[i];j++){
			llo co=tt-(it[i-1]-1)*bb;
			if(co<=0){
				continue;
			}
			co-=(j-it[i-1])*cc;
			if(co<0){
				continue;
			}
			llo co2=tt-(it[i-1]-1)*bb;

			llo kk=min(1+co/aa+max(min(co2/aa,j-it[i-1]-1),(llo)0),it[i]-it[i-1]-1);
		//	aa.pb({j,kk});
			/*if(j>0){
				kk-=dd[i][j-1];
			}*/
			if(j==it[i-1]){
				tot2=kk-1;
			}
			else{
				tot=max(tot,kk);
			}
	//		cout<<i<<" "<<j<<" "<<kk<<endl;
		}
		pre[i][0]=max(tot2,(llo)0);
		pre[i][1]=tot;
	//	cout<<i<<"::"<<tot2<<"::"<<tot<<endl;
	}
	llo dp[m][k+1];
	for(llo i=0;i<m;i++){
		for(llo j=0;j<k+1;j++){
			dp[i][j]=0;
		}
	}
	for(llo i=1;i<m;i++){
		dp[i][0]=0;
		for(llo j=1;j<k+1;j++){
			dp[i][j]=pre[i][1]+dp[i-1][j-1];
			dp[i][j]=max(dp[i][j],dp[i-1][j]+pre[i][0]);
			/*if(j<=k-m){
				cout<<i<<","<<j<<","<<dp[i][j]<<endl;
			}*/
			dp[i][j]=max(dp[i][j],dp[i][j-1]);
		}
	}
	cout<<ans+dp[m-1][k-m];


	return 0;
}

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