Submission #25401

#	Time	Username	Problem	Language	Result	Execution time	Memory
25401		youngyojun	Watching (JOI13_watching)	C++11	100 / 100	263 ms	17744 KiB

watching

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (2005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int d[MAXN][MAXN];
int BL[MAXN], SL[MAXN];
int A[MAXN];
int N, P, Q;

bool f(const int W) {
	for(int i = N, j = N; i; i--) {
		for(; j && A[i]-W < A[j]; j--);
		SL[i] = j;
	}
	for(int i = N, j = N; i; i--) {
		for(; j && A[i]-2*W < A[j]; j--);
		BL[i] = j;
	}
	for(int i = 1; i <= N; i++) for(int j = 0; j <= Q; j++) {
		int &ret = d[i][j];
		ret = d[SL[i]][j] + 1;
		if(j) upmin(ret, d[BL[i]][j-1]);
	}
	for(int i = 0; i <= Q; i++) if(d[N][i] <= P) return true;
	return false;
}
int getAns() {
	if(N <= P || N <= Q) return 1;
	int s = 1, e = INF; for(int mid; s < e;) {
		mid = (s+e)/2;
		if(f(mid)) e = mid; else s = mid+1;
	}
	return s;
}
int main() {
	scanf("%d%d%d", &N, &P, &Q);
	for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
	sort(A+1, A+N+1);
	printf("%d\n", getAns());
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:68:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &P, &Q);
                             ^
watching.cpp:69:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
                                                ^

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