oj.uz

Submission #444352

# Submission time Handle Problem Language Result Execution time Memory
444352 2021-07-13T18:08:40 Z fuad27 Watching (JOI13_watching) C++14
0 / 100
 490 ms 32008 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, p, q, a = 0 , b;
vector<int> A;
vector<vector<int>> dp(2010, vector<int> (2010, 0));
bool check(int w) {
	a = 0;
	dp[0][0] = 0;
	int I = min(n, q);
	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 = 0, ans = 0;
	while(l<=r) {
		int mid = (l+r)/2;
		if(check(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31948 KB Output is correct
2 Correct 15 ms 31988 KB Output is correct
3 Correct 15 ms 31916 KB Output is correct
4 Incorrect 15 ms 31900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31964 KB Output is correct
2 Correct 15 ms 31916 KB Output is correct
3 Correct 490 ms 32008 KB Output is correct
4 Incorrect 24 ms 32008 KB Output isn't correct
5 Halted 0 ms 0 KB -