Submission #359268

#	Time	Username	Problem	Language	Result	Execution time	Memory
359268		pure_mem	Watching (JOI13_watching)	C++14	100 / 100	795 ms	16256 KiB

watching

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 2e3 + 3;

int n, p, q, a[N], dp[N][N], nx1[N], nx2[N];
queue< pair<int, int> > ord;

bool check(int lk){
	if(p + q >= n)
		return 1;
	memset(dp, -1, sizeof(dp));
	for(int i = 1;i <= n;i++){
		nx1[i] = upper_bound(a + i, a + n + 1, a[i] + lk - 1) - a - 1;
		nx2[i] = upper_bound(a + i, a + n + 1, a[i] + lk + lk - 1) - a - 1;
	}
	dp[0][0] = 0; 
	ord.push(MP(0, 0));
	bool good = 0;
	while(!ord.empty()){
		int x = ord.front().X, y = ord.front().Y;
		ord.pop();
		if(x - 1 >= 0)
			dp[x][y] = max(dp[x][y], nx1[dp[x - 1][y] + 1]);
		if(y - 1 >= 0)
			dp[x][y] = max(dp[x][y], nx2[dp[x][y - 1] + 1]);
		if(x + 1 <= p){
			if(dp[x + 1][y] == -1)
				ord.push(MP(x + 1, y));
			dp[x + 1][y] = max(dp[x + 1][y], dp[x][y]);
		}
		if(y + 1 <= q){
			if(dp[x][y + 1] == -1)
				ord.push(MP(x, y + 1));
			dp[x][y + 1] = max(dp[x][y + 1], dp[x][y]);
		}
		good |= dp[x][y] == n;
	}
	return good;	
}

int main () {		
	scanf("%d %d %d", &n, &p, &q);
	p = min(p, n), q = min(q, n);
	for(int i = 1;i <= n;i++)
		scanf("%d", a + i);
	sort(a + 1, a + n + 1);
	int tl = 1, tr = 1000000000, tp = 1000000000;
	while(tl <= tr){
		int tm = (tl + tr) / 2;
		//cerr << tm << " " << check(tm) << "\n";
		if(check(tm))
			tr = tm - 1, tp = tm;
		else
			tl = tm + 1;
	}
	printf("%d", tp);
}         

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d %d %d", &n, &p, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%d", a + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50