oj.uz

Submission #25419

# Submission time Handle Problem Language Result Execution time Memory
25419 2017-06-22T06:17:58 Z kajebiii Watching (JOI13_watching) C++14
50 / 100
 36 ms 6016 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 1e3 + 10;

int N, P, Q, Nr[MAX_N];
int L[2][MAX_N], Dy[MAX_N][MAX_N];
int main() {
	cin >> N >> P >> Q;
	REPO(i, N) scanf("%d", &Nr[i]);
	sort(Nr+1, Nr+N+1);

	P = min(N, P), Q = min(N, Q);

	int ans = -1;
	for(int l=1, r=1e9; l<=r; ) {
		int m = (l+r) >> 1;
		int w[2] = {m, 2*m};
		for(int k=0; k<2; k++) {
			int l = 1;
			for(int i=1; i<=N; i++) {
				while(Nr[i] - w[k] >= Nr[l]) l++;
				L[k][i] = l;
			}
		}
		Dy[0][0] = 0;
		for(int i=1; i<=N; i++) {
			for(int j=0; j<=P; j++) Dy[i][j] = INF;
			for(int j=0; j<=P; j++) {
				if(j) Dy[i][j] = min(Dy[i][j], Dy[L[0][i]-1][j-1]);
				Dy[i][j] = min(Dy[i][j], Dy[L[1][i]-1][j] + 1);
			}
		}
		bool isCan = false;
		for(int j=0; j<=P; j++) if(Dy[N][j] <= Q) isCan = true;
		if(isCan) ans = m, r = m-1;
		else l = m+1;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:22:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REPO(i, N) scanf("%d", &Nr[i]);
                                ^

Subtask #1
50.0 / 50.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 6016 KB Execution timed out (wall clock limit exceeded)
2 Halted 0 ms 0 KB -