oj.uz

Submission #274783

# Submission time Handle Problem Language Result Execution time Memory
274783 2020-08-19T15:37:25 Z tincamatei Watching (JOI13_watching) C++14
100 / 100
 829 ms 16120 KB 
    #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

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

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 3 ms 768 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 16120 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 756 ms 16080 KB Output is correct
4 Correct 767 ms 16072 KB Output is correct
5 Correct 764 ms 16080 KB Output is correct
6 Correct 759 ms 16120 KB Output is correct
7 Correct 781 ms 16076 KB Output is correct
8 Correct 789 ms 16076 KB Output is correct
9 Correct 806 ms 16072 KB Output is correct
10 Correct 829 ms 16076 KB Output is correct
11 Correct 796 ms 16120 KB Output is correct
12 Correct 816 ms 16120 KB Output is correct
13 Correct 797 ms 16076 KB Output is correct
14 Correct 806 ms 16120 KB Output is correct
15 Correct 793 ms 16120 KB Output is correct