Submission #949907

#	Time	Username	Problem	Language	Result	Execution time	Memory
949907		starchan	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	61 ms	92720 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
const int SMX = 3e3+5;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int dp[SMX][SMX];
int cost[SMX][SMX];
void dnc(int k, int l, int r, int L, int R)//answer for all l, r lies between L and R.
{
	if(l > r)
		return;
	int m = (l+r)/2;
	in bet = {-INF, -INF};
	for(int opt = L; opt <= min(R, m); opt++)
		bet = max(bet, {dp[k-1][opt]+cost[k][m-opt], opt});
	dp[k][m] = bet.f; int opt = bet.s;
	dnc(k, l, m-1, L, opt);
	dnc(k, m+1, r, opt, R);
	return;
}
signed main()
{
	fast();
	int n, m, k, a, b, c, T;
	cin >> n >> m >> k >> a >> b >> c >> T;
	vector<int> v;
	v.pb(0);
	for(int i = 1; i <= m; i++)
	{
		int x; cin >> x;
		v.pb(x);
	}
	v.pb(n+1);
	for(int i = 1; i <= m; i++)
	{
		int t = b*(v[i]-1);
		int loc = v[i];
		if(t > T)
			break;
		int prev = 0;
		for(int n = 0; n <= k; n++)
		{
			if(loc >= v[i+1])
			{
				cost[i][n] = prev;
				continue;
			}
			if(t > T)
			{
				cost[i][n] = prev;
				continue;
			}
			int ell = (T-t)/a;
			//t, t+a, t+2a, .., t + ell a
			//loc, loc+1, .., loc + ell
			ell = min(ell, v[i+1]-1-loc);
			cost[i][n] = prev + (ell+1);
			t+=((ell+1)*c);
			loc+=(ell+1);
			prev = cost[i][n];
		}
	}
	/*for(int i = 1; i <= m; i++)
	{
		printf("For the %dth gap between %d and %d: ", i, v[i], v[i+1]);
		cout << "\n";
		for(int j = 0; j <= k; j++)
			cout << cost[i][j] << " ";
		cout << endl;
	}*/
	for(int i = 1; i <= m; i++)
	{
		dnc(i, 0, k, 0, k);

		/*for(int j = 0; j <= k; j++)
		{
			in ok = {-INF, -INF};
			for(int r = 0; r <= j; r++)
				ok = max(ok, {dp[i-1][j-r]+cost[i][r], r});
			dp[i][j] = ok.f;
			//cout << "r: " << ok.s << " j-r : " << j-ok.s << endl;
		}*/
		//cout << "----------------" << endl;
	}
	cout << dp[m][k-m]-1;
	return 0;
}	

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