oj.uz

Submission #34571

# Submission time Handle Problem Language Result Execution time Memory
34571 2017-11-13T04:19:41 Z sinhriv Watching (JOI13_watching) C++14
50 / 100
 1000 ms 96744 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2202;

int n, p, q;
int a[N];
int f[N][N];

struct SegmentTreeMin{
	int it[N * 4];

	#define mid ((l + r) >> 1)

	void build(int x, int l, int r){
		it[x] = 1e9;
		if(l == r) {
			return;
		}
		build(x + x, l, mid);
		build(x + x + 1, mid + 1, r);
	}

	void modify(int x, int l, int r, int pos, int val){
		if(l > pos || r < pos) return;
		it[x] = min(it[x], val);
		if(l == r) return;
		modify(x + x, l, mid, pos, val);
		modify(x + x + 1, mid + 1, r, pos, val);
	}

	int query(int x, int l, int r, int u, int v){
		if(l > v || r < u) return 1e9;
		if(l >= u && r <= v) return it[x];
		return min(query(x + x, l, mid, u, v), query(x + x + 1, mid + 1, r, u, v));
	}
}g[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;
	
		memset(f, 60, sizeof f);


		f[0][0] = 0;
		for(int i = 0; i <= p; ++i){
			g[i].build(1, 0, n);
		}

		g[0].modify(1, 0, n, 0, 0);

		bool ok = false, debug = false;


		
		for(int i = 1; i <= n; ++i){
			for(int j = 0; j <= min(i, p); ++j){
				if(j > 0){
					int pos = lower_bound(a + 1, a + n + 1, a[i] - w + 1) - a;
					f[i][j] = g[j - 1].query(1, 0, n, pos - 1, i);
				}
				int pos = lower_bound(a + 1, a + n + 1, a[i] - w - w + 1) - a;
				f[i][j] = min(f[i][j], g[j].query(1, 0, n, pos - 1, i) + 1);


				if(i == n && f[i][j] <= q){
					ok = true;
				}
				g[j].modify(1, 0, n, i, f[i][j]);
			}
		}



		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:71:20: warning: unused variable 'debug' [-Wunused-variable]
   bool ok = false, debug = false;
                    ^
watching.cpp:42: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:45: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:48: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 46 ms 96744 KB Output is correct
2 Correct 69 ms 96744 KB Output is correct
3 Correct 79 ms 96744 KB Output is correct
4 Correct 146 ms 96744 KB Output is correct
5 Correct 93 ms 96744 KB Output is correct
6 Correct 136 ms 96744 KB Output is correct
7 Correct 89 ms 96744 KB Output is correct
8 Correct 103 ms 96744 KB Output is correct
9 Correct 129 ms 96744 KB Output is correct
10 Correct 106 ms 96744 KB Output is correct
11 Correct 83 ms 96744 KB Output is correct
12 Correct 93 ms 96744 KB Output is correct
13 Correct 53 ms 96744 KB Output is correct
14 Correct 69 ms 96744 KB Output is correct
15 Correct 63 ms 96744 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 96744 KB Output is correct
2 Correct 56 ms 96744 KB Output is correct
3 Execution timed out 1000 ms 96744 KB Execution timed out
4 Halted 0 ms 0 KB -