| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25400 |
2017-06-22T04:33:49 Z |
윤교준(#1068) |
Watching (JOI13_watching) |
C++11 |
|
279 ms |
17744 KB |
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (2005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
int d[MAXN][MAXN];
int BL[MAXN], SL[MAXN];
int A[MAXN];
int N, P, Q;
bool f(const int W) {
for(int i = N, j = N; i; i--) {
for(; j && A[i]-W < A[j]; j--);
SL[i] = j;
}
for(int i = N, j = N; i; i--) {
for(; j && A[i]-2*W < A[j]; j--);
BL[i] = j;
}
for(int i = 1; i <= N; i++) for(int j = 0; j <= Q; j++) {
int &ret = d[i][j];
ret = d[SL[i]][j] + 1;
if(j) upmin(ret, d[BL[i]][j-1]);
}
for(int i = 0; i <= Q; i++) if(d[N][i] <= P) return true;
return false;
}
int getAns() {
if(N <= P || N <= Q) return 1;
int s = 1, e = INF; for(int mid; s < e;) {
mid = (s+e)/2;
if(f(mid)) e = mid; else s = mid+1;
}
return s;
}
int main() {
scanf("%d%d%d", &N, &P, &Q);
for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
sort(A+1, A+N+1);
printf("%d\n", getAns());
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:68: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:69:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 3 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 4 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 5 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 6 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 7 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 8 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 9 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 10 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 11 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 12 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 13 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 14 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 15 |
Correct |
0 ms |
17744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 3 |
Correct |
216 ms |
17744 KB |
Output is correct |
| 4 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 5 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 6 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 7 |
Correct |
0 ms |
17744 KB |
Output is correct |
| 8 |
Correct |
109 ms |
17744 KB |
Output is correct |
| 9 |
Correct |
23 ms |
17744 KB |
Output is correct |
| 10 |
Correct |
16 ms |
17744 KB |
Output is correct |
| 11 |
Correct |
279 ms |
17744 KB |
Output is correct |
| 12 |
Correct |
153 ms |
17744 KB |
Output is correct |
| 13 |
Correct |
3 ms |
17744 KB |
Output is correct |
| 14 |
Correct |
6 ms |
17744 KB |
Output is correct |
| 15 |
Correct |
3 ms |
17744 KB |
Output is correct |
