oj.uz

Submission #73192

# Submission time Handle Problem Language Result Execution time Memory
73192 2018-08-28T03:51:13 Z zscoder Watching (JOI13_watching) C++17
50 / 100
 1000 ms 16712 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

ll a[2001];
int dp[2001][2001];

int n, p, q;


bool can(ll v)
{
	memset(dp, -1, sizeof(dp));
	for(int i = 0; i <= p; i++)
	{
		for(int j = 0; j <= q; j++)
		{
			if(dp[i][j] == n-1) return true;
			dp[i+1][j]=max(dp[i+1][j], int(upper_bound(a, a+n, a[dp[i][j]+1]+v-1) - a - 1));
			dp[i][j+1] = max(dp[i][j+1], int(upper_bound(a,a+n,a[dp[i][j]+1]+2*v-1) - a - 1));
		}
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> p >> q;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	ll ans = -1;
	ll lo = 1; ll hi = ll(1e9);
	ll mid;
	while(lo <= hi)
	{
		mid = (lo+hi)>>1;
		if(can(mid))
		{
			hi = mid - 1;
			ans = mid;
		}
		else
		{
			lo = mid + 1;
		}
	}
	cout << ans;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 15992 KB Output is correct
2 Correct 100 ms 16112 KB Output is correct
3 Correct 118 ms 16172 KB Output is correct
4 Correct 53 ms 16172 KB Output is correct
5 Correct 110 ms 16268 KB Output is correct
6 Correct 102 ms 16268 KB Output is correct
7 Correct 106 ms 16508 KB Output is correct
8 Correct 46 ms 16508 KB Output is correct
9 Correct 105 ms 16508 KB Output is correct
10 Correct 113 ms 16508 KB Output is correct
11 Correct 112 ms 16508 KB Output is correct
12 Correct 111 ms 16508 KB Output is correct
13 Correct 126 ms 16508 KB Output is correct
14 Correct 117 ms 16532 KB Output is correct
15 Correct 114 ms 16532 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 16532 KB Output is correct
2 Correct 120 ms 16532 KB Output is correct
3 Correct 627 ms 16552 KB Output is correct
4 Correct 262 ms 16552 KB Output is correct
5 Correct 123 ms 16552 KB Output is correct
6 Correct 112 ms 16552 KB Output is correct
7 Correct 83 ms 16552 KB Output is correct
8 Correct 298 ms 16584 KB Output is correct
9 Correct 267 ms 16584 KB Output is correct
10 Correct 281 ms 16708 KB Output is correct
11 Correct 247 ms 16708 KB Output is correct
12 Execution timed out 1088 ms 16712 KB Time limit exceeded
13 Halted 0 ms 0 KB -