| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 85373 |
2018-11-19T13:59:42 Z |
psmao |
Watching (JOI13_watching) |
C++14 |
|
419 ms |
16932 KB |
#include <bits/stdc++.h>
using namespace std;
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define pb push_back
#define mp make_pair
const int maxn = 2005;
int n, p, q, a[maxn];
int dp[maxn][maxn], g[maxn], gg[maxn];
bool judge(int x)
{
fo(i,1,n) fo(j,0,p) dp[i][j] = 1<<30;
dp[0][0] = 0;
int l, r, mid, pos;
fo(i,1,n)
{
l = 1; r = i; pos = 0;
while(l <= r)
{
mid = l + r >> 1;
if(a[i]-x+1<=a[mid]) pos = mid, r = mid - 1;
else l = mid + 1;
}
g[i] = pos;
l = 1; r = i; pos = 0;
while(l <= r)
{
mid = l + r >> 1;
if(a[i]-x*2+1<=a[mid]) pos = mid, r = mid - 1;
else l = mid + 1;
}
gg[i] = pos;
}
fo(i,1,n) fo(j,0,p)
{
if(j) dp[i][j] = min(dp[i][j], dp[g[i]-1][j-1]);
dp[i][j] = min(dp[i][j], dp[gg[i]-1][j]+1);
}
fo(i,0,p) if(dp[n][i]<=q) return true;
return false;
}
void task1()
{
if(p >= n || q >= n)
{
printf("1");
return;
}
int l, r, mid, ans;
l = 1; r = 1000000000;
while(l <= r)
{
mid = l + r >> 1;
if(judge(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d",ans);
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d%d%d",&n,&p,&q);
fo(i,1,n) scanf("%d",&a[i]);
sort(a+1,a+n+1);
task1();
return 0;
}
Compilation message
watching.cpp: In function 'bool judge(int)':
watching.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid = l + r >> 1;
~~^~~
watching.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid = l + r >> 1;
~~^~~
watching.cpp: In function 'void task1()':
watching.cpp:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid = l + r >> 1;
~~^~~
watching.cpp: In function 'int main()':
watching.cpp:68:7: 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:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fo(i,1,n) scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
888 KB |
Output is correct |
| 2 |
Correct |
2 ms |
888 KB |
Output is correct |
| 3 |
Correct |
2 ms |
888 KB |
Output is correct |
| 4 |
Correct |
2 ms |
888 KB |
Output is correct |
| 5 |
Correct |
2 ms |
888 KB |
Output is correct |
| 6 |
Correct |
2 ms |
888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1196 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1200 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1220 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1220 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1228 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1232 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 14 |
Correct |
3 ms |
1240 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
8936 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8936 KB |
Output is correct |
| 3 |
Correct |
336 ms |
16636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
16636 KB |
Output is correct |
| 5 |
Correct |
2 ms |
16636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
16636 KB |
Output is correct |
| 7 |
Correct |
19 ms |
16636 KB |
Output is correct |
| 8 |
Correct |
42 ms |
16636 KB |
Output is correct |
| 9 |
Correct |
179 ms |
16636 KB |
Output is correct |
| 10 |
Correct |
419 ms |
16868 KB |
Output is correct |
| 11 |
Correct |
35 ms |
16868 KB |
Output is correct |
| 12 |
Correct |
229 ms |
16932 KB |
Output is correct |
| 13 |
Correct |
16 ms |
16932 KB |
Output is correct |
| 14 |
Correct |
17 ms |
16932 KB |
Output is correct |
| 15 |
Correct |
16 ms |
16932 KB |
Output is correct |
