oj.uz

Submission #949907

# Submission time Handle Problem Language Result Execution time Memory
949907 2024-03-19T21:58:32 Z starchan Semiexpress (JOI17_semiexpress) C++17
100 / 100
 61 ms 92720 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 2544 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 2544 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 2544 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 48 ms 42732 KB Output is correct
20 Correct 41 ms 40788 KB Output is correct
21 Correct 19 ms 36188 KB Output is correct
22 Correct 30 ms 44632 KB Output is correct
23 Correct 61 ms 81748 KB Output is correct
24 Correct 25 ms 58968 KB Output is correct
25 Correct 13 ms 23644 KB Output is correct
26 Correct 56 ms 92720 KB Output is correct
27 Correct 40 ms 73280 KB Output is correct
28 Correct 44 ms 75188 KB Output is correct
29 Correct 12 ms 25892 KB Output is correct
30 Correct 5 ms 7772 KB Output is correct