oj.uz

Submission #444361

# Submission time Handle Problem Language Result Execution time Memory
444361 2021-07-13T18:28:24 Z fuad27 Watching (JOI13_watching) C++14
100 / 100
 579 ms 32152 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, p, q;
vector<int> A;
vector<vector<int>> dp(2010, vector<int> (2010, 0));
bool can(int w) {
	int a = 0, b = 0;
	dp[0][0] = 0;
	int I = min(n, p);
	int J = min(n, q);
	for(int i = 0;i<=I;i++) {
		for(int j = 0;j<=J;j++) {
			if(i == 0 and j == 0) continue;
            		if(i > 0)
            		{
                		a=dp[i-1][j];
				b = a;
                		while(a<n and A[b]+w-1>=A[a])
					a++;
            		}
            		dp[i][j]=a;
        	    	if(j > 0)
	        	{
	            		a=dp[i][j-1];
				b = a;
        			while(a<n and A[b]+2*w-1>=A[a])
					a++;
            		}
            		dp[i][j]=max(a, dp[i][j]);
		}
	}
	return (dp[I][J]>=n);
}
int32_t main () {
	cin >> n >> p >> q;
	for(int i = 0;i<n;i++) {
		int ai;
		cin >> ai;
		A.push_back(ai);
	}
	sort(A.begin(), A.end());
	int r = 1e9, l = 1, ans = 0;
	while(l<=r) {
		int mid = (l+r)/2;
		if(can(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	cout<<l<<endl;
	return 0;
}

Compilation message

watching.cpp: In function 'int32_t main()':
watching.cpp:43:22: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   43 |  int r = 1e9, l = 1, ans = 0;
      |                      ^~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31948 KB Output is correct
2 Correct 15 ms 32004 KB Output is correct
3 Correct 15 ms 31992 KB Output is correct
4 Correct 15 ms 31948 KB Output is correct
5 Correct 15 ms 31936 KB Output is correct
6 Correct 19 ms 31988 KB Output is correct
7 Correct 17 ms 31956 KB Output is correct
8 Correct 15 ms 31928 KB Output is correct
9 Correct 15 ms 32008 KB Output is correct
10 Correct 15 ms 32004 KB Output is correct
11 Correct 15 ms 31904 KB Output is correct
12 Correct 17 ms 31960 KB Output is correct
13 Correct 15 ms 31948 KB Output is correct
14 Correct 15 ms 31936 KB Output is correct
15 Correct 15 ms 31912 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31996 KB Output is correct
2 Correct 16 ms 32076 KB Output is correct
3 Correct 401 ms 32008 KB Output is correct
4 Correct 61 ms 31948 KB Output is correct
5 Correct 48 ms 32028 KB Output is correct
6 Correct 579 ms 32036 KB Output is correct
7 Correct 17 ms 31948 KB Output is correct
8 Correct 49 ms 32152 KB Output is correct
9 Correct 49 ms 32016 KB Output is correct
10 Correct 54 ms 31948 KB Output is correct
11 Correct 53 ms 31948 KB Output is correct
12 Correct 199 ms 32036 KB Output is correct
13 Correct 17 ms 31932 KB Output is correct
14 Correct 18 ms 31948 KB Output is correct
15 Correct 17 ms 31948 KB Output is correct