oj.uz

Submission #802530

# Submission time Handle Problem Language Result Execution time Memory
802530 2023-08-02T12:41:11 Z KN200711 Watching (JOI13_watching) C++14
0 / 100
 13 ms 9324 KB 
# include <bits/stdc++.h>
# define ll long long
using namespace std;

int N, P, Q;
vector<int> arr;

int mn[2001][2001];
int edge[2][2001];

bool cek(int a) {
	// set edge nya dulu
	for(int i=0;i<N;i++) {
		int T = arr[i] + a - 1;
		edge[0][i] = upper_bound(arr.begin(), arr.end(), T) - arr.begin();
		T += a;
		edge[1][i] = upper_bound(arr.begin(), arr.end(), T) - arr.begin();
		
	//	if(a == 4) cout<<i<<" "<<edge[0][i]<<" "<<edge[1][i]<<endl;
	}
	
	if(P < Q) {
		for(int d=0;d<=N;d++) {
			for(int a=0;a<=P;a++) mn[d][a] = 1e9;
		}
		priority_queue< pair<int, pair<int, int> > > PQ;
		PQ.push(make_pair(0, make_pair(0, 0)));
		
		while(!PQ.empty()) {
			int x, y, z;
			x = PQ.top().second.first;
			y = PQ.top().second.second;
			z = PQ.top().first;
			PQ.pop();
			if(-z > Q) continue;
			if(mn[x][-y] != 1e9) continue;
		//	if(a == 1) cout<<x<<" "<<y<<" "<<z<<endl;
			mn[x][-y] = z;
			if(x == N) return 1;
			
			PQ.push(make_pair(z, make_pair(y-1, edge[0][x])));
			PQ.push(make_pair(z-1, make_pair(y, edge[1][x])));
		}
		return 0;
	} else {
		for(int d=0;d<=N;d++) {
			for(int a=0;a<=Q;a++) mn[d][a] = 1e9;
		}
		priority_queue< pair<int, pair<int, int> > > PQ;
		PQ.push(make_pair(0, make_pair(0, 0)));
		
		while(!PQ.empty()) {
			int x, y, z;
			x = PQ.top().second.first;
			y = PQ.top().second.second;
			z = PQ.top().first;
			PQ.pop();
			if(-z > P) continue;
			if(mn[x][-y] != 1e9) continue;
		//	if(a == 1) cout<<x<<" "<<y<<" "<<z<<endl;
			mn[x][-y] = z;
			if(x == N) return 1;
			
			PQ.push(make_pair(z, make_pair(edge[1][x], y-1)));
			PQ.push(make_pair(z-1, make_pair(edge[0][x], y)));
		}
		return 0;
	}
	for(int d=0;d<=N;d++) {
		for(int a=0;a<=P;a++) mn[d][a] = 1e9;
	}
	priority_queue< pair<int, pair<int, int> > > PQ;
	PQ.push(make_pair(0, make_pair(0, 0)));
	
	while(!PQ.empty()) {
		int x, y, z;
		x = PQ.top().second.second;
		y = PQ.top().second.first;
		z = PQ.top().first;
		PQ.pop();
		if(-z > Q) continue;
		if(mn[x][-y] != 1e9) continue;
	//	if(a == 1) cout<<x<<" "<<y<<" "<<z<<endl;
		mn[x][-y] = z;
		if(x == N) return 1;
		
		PQ.push(make_pair(z, make_pair(edge[0][x], y - 1)));
		PQ.push(make_pair(z-1, make_pair(edge[1][x], y)));
	}
	return 0;
}

int main() {
	scanf("%d %d %d", &N, &P, &Q);
	arr.resize(N);
	for(int i=0;i<N;i++) scanf("%d", &arr[i]);
	sort(arr.begin(), arr.end());
	
	if(P + Q >= N) {
		printf("1\n");
		return 0;
	}
	
//	cout<<cek(4)<<endl;
	int l = 1, r = 1e9, ans = -1;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(cek(mid)) {
			ans = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	printf("%d\n", ans);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d %d %d", &N, &P, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:96:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  for(int i=0;i<N;i++) scanf("%d", &arr[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Incorrect 1 ms 596 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8364 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 8 ms 8380 KB Output is correct
8 Incorrect 13 ms 9324 KB Output isn't correct
9 Halted 0 ms 0 KB -