oj.uz

Submission #963807

# Submission time Handle Problem Language Result Execution time Memory
963807 2024-04-15T17:31:44 Z starchan Watching (JOI13_watching) C++17
100 / 100
 330 ms 94268 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)1e6
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e3+2;
	
int dp[MX][3*MX];

signed main()
{
	fast();
	int n, p, q;
	cin >> n >> p >> q;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a.begin()+1, a.end());
	a[0] = -INF;
	if(p >= n)
	{
		cout << "1\n";
		return 0;
	}
	if(q >= n)
	{
		cout << "1\n";
		return 0;
	}
	int ck = 0;
	for(int up = (1ll<<33); up >>= 1;)
	{
		int w = ck+up;
		//dp[i][j] stores INF, if it is not possible to cover [1, i] using at most j width stones.
		//dp[i][j] = stores maximum number of 2w width getaways possible with scamming.
		for(int i = 1; i <= n; i++)
			dp[i][0] = -INF;
		for(int i = 0; i <= (p+2*q); i++)
			dp[0][i] = (i/2);
		int lp1, lp2; lp1 = lp2 = 0;
		for(int i = 1; i <= n; i++)
		{
			while(((lp1+1) <= n) && (a[lp1+1] <= (a[i]-w)))
				lp1++;
			while(((lp2+1) <= n) && (a[lp2+1] <= (a[i]-(2*w))))
				lp2++;
			dp[i][1] = dp[lp1][0];
			for(int j = 2; j <= p+2*q; j++)
				dp[i][j] = max(dp[lp1][j-1], 1+dp[lp2][j-2]);
		}
		if(dp[n][p+2*q] < q)
			ck = w;
	}
	ck++;
	cout << ck << "\n";
	return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6608 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6488 KB Output is correct
12 Correct 2 ms 6488 KB Output is correct
13 Correct 2 ms 6632 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 92764 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 330 ms 94268 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 14 ms 93004 KB Output is correct
8 Correct 120 ms 93440 KB Output is correct
9 Correct 85 ms 93252 KB Output is correct
10 Correct 150 ms 93564 KB Output is correct
11 Correct 261 ms 94032 KB Output is correct
12 Correct 198 ms 93824 KB Output is correct
13 Correct 17 ms 92996 KB Output is correct
14 Correct 14 ms 92764 KB Output is correct
15 Correct 14 ms 92764 KB Output is correct