Submission #102542

#	Time	Username	Problem	Language	Result	Execution time	Memory
102542		tincamatei	Watching (JOI13_watching)	C++14	100 / 100	609 ms	16120 KiB

watching

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000;

int v[MAX_N];
int smallNext[1+MAX_N], bigNext[1+MAX_N];
int dp[1+MAX_N][1+MAX_N];

void getNexts(int n, int w, int *nextP) {
	int lastp = 0;
	for(int i = 0; i < n; ++i) {
		while(lastp < n - 1 && v[lastp + 1] < v[i] + w)
			++lastp;
		nextP[i] = lastp;
	}

	nextP[n] = n - 1;
}

void runDp(int n, int w) {
	getNexts(n, w, smallNext);
	getNexts(n, 2 * w, bigNext);
	
	for(int i = 0; i <= n; ++i)
		for(int j = 0; j <= n; ++j) {
			dp[i][j] = 0;
			if(i > 0)
				dp[i][j] = max(dp[i][j], smallNext[dp[i - 1][j]] + 1);
			if(j > 0)
				dp[i][j] = max(dp[i][j], bigNext[dp[i][j - 1]] + 1);
		}
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n, p, q, st, dr;
	
	fscanf(fin, "%d%d%d", &n, &p, &q);
	for(int i = 0; i < n; ++i)
		fscanf(fin, "%d", &v[i]);

	sort(v, v + n);

	st = 0;
	dr = 1000000000;

	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		runDp(n, mid);
		
		if(dp[min(p, n)][min(q, n)] == n)
			dr = mid;
		else
			st = mid;
	}
	
	fprintf(fout, "%d", dr);

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:47:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d%d%d", &n, &p, &q);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:49:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d", &v[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~

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