oj.uz

Submission #34576

# Submission time Handle Problem Language Result Execution time Memory
34576 2017-11-13T05:44:00 Z sinhriv Watching (JOI13_watching) C++14
100 / 100
 809 ms 20980 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2202;
 
int n, p, q;
int a[N];
int f[N][N];
 
int one[N];
int two[N];

int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}
 
	scanf("%d%d%d", &n, &p, &q);
 
	for(int i = 1; i <= n; ++i){
		scanf("%d", a + i);
	}
 
	p = min(p, n);
	q = min(q, n);
 
	sort(a + 1, a + n + 1);
 
	int low = 1, high = 1e9, ans = 1e9;
 
	while(low <= high){
		int w = (low + high) >> 1;
	
		for(int i = 0; i <= n; ++i){
			for(int j = 0; j <= n; ++j){
				f[i][j] = 1e9;
			}
		}
		f[0][0] = 0;
 
		bool ok = false, debug = false;
 
		int pterOne = 0, pterTwo = 0;

		for(int i = 1; i <= n; ++i){
			while(a[i] - a[pterOne + 1] + 1 > w) ++pterOne;
			while(a[i] - a[pterTwo + 1] + 1 > w + w) ++pterTwo;
			
			one[i] = pterOne; 
			two[i] = pterTwo;				
		}

			
		for(int j = 0; j <= p; ++j){
 

			for(int i = 1; i <= n; ++i){


				if(j > 0) f[i][j] = min(f[i][j], f[one[i]][j - 1]);
				f[i][j] = min(f[i][j], f[two[i]][j] + 1);
				
 
				if(i == n && f[i][j] <= q){
					ok = true;
					break;
				}
			}
			if(ok) break;
		}
 
 
		if(ok == false){
			low = w + 1;
		}
		else{
			ans = w;
			high = w - 1;
		}
	}
 
	cout << ans;
 
	return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:42:20: warning: unused variable 'debug' [-Wunused-variable]
   bool ok = false, debug = false;
                    ^
watching.cpp:16:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
watching.cpp:19: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:22:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
                     ^

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 20980 KB Output is correct
2 Correct 0 ms 20980 KB Output is correct
3 Correct 149 ms 20980 KB Output is correct
4 Correct 736 ms 20980 KB Output is correct
5 Correct 86 ms 20980 KB Output is correct
6 Correct 99 ms 20980 KB Output is correct
7 Correct 96 ms 20980 KB Output is correct
8 Correct 136 ms 20980 KB Output is correct
9 Correct 446 ms 20980 KB Output is correct
10 Correct 809 ms 20980 KB Output is correct
11 Correct 109 ms 20980 KB Output is correct
12 Correct 363 ms 20980 KB Output is correct
13 Correct 99 ms 20980 KB Output is correct
14 Correct 109 ms 20980 KB Output is correct
15 Correct 99 ms 20980 KB Output is correct