oj.uz

답안 #92675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92675 2019-01-04T09:53:21 Z LittleFlowers__ 구경하기 (JOI13_watching) C++14
50 / 100
 1000 ms 32120 KB 
#include <bits/stdc++.h>
#define int long long
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define reset(f, x) memset(f, x, sizeof(f))
using namespace std;
const int N=2010;
int n,p,q;
int a[N];
int f[N][N];
bool C(int x)
{
    reset(f,-1);
    f[0][p]=q;
    forinc(i,0,n-1) forinc(j,0,p) if(f[i][j]>-1)
    {
        if(j)
        {
            int t=upper_bound(a+1,a+n+1,a[i+1]+x-1)-a-1;
            f[t][j-1]=max(f[t][j-1],f[i][j]);
        }
        if(f[i][j])
        {
            int t=upper_bound(a+1,a+n+1,a[i+1]+x*2-1)-a-1;
            f[t][j]=max(f[t][j],f[i][j]-1);
        }
    }
    forinc(i,0,p) if(f[n][i]>-1) return 1;
    return 0;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("WATCHING.inp","r",stdin);
    cin>>n>>p>>q;p=min(p,n),q=min(q,n);
    for(int i=1; i<=n; ++i) cin>>a[i];
    sort(a+1,a+n+1);
    int l=1,m,r=1e9,ans;
    while(l<=r)
    {
        m=l+(r-l)/2;
        if(C(m)) ans=m,r=m-1;
        else l=m+1;
    }
    cout<<ans;
}

Compilation message

watching.cpp:30:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 32000 KB Output is correct
2 Correct 128 ms 31992 KB Output is correct
3 Correct 143 ms 32036 KB Output is correct
4 Correct 393 ms 31992 KB Output is correct
5 Correct 143 ms 31992 KB Output is correct
6 Correct 125 ms 31964 KB Output is correct
7 Correct 129 ms 32004 KB Output is correct
8 Correct 218 ms 32004 KB Output is correct
9 Correct 235 ms 32120 KB Output is correct
10 Correct 131 ms 31992 KB Output is correct
11 Correct 200 ms 32000 KB Output is correct
12 Correct 236 ms 32036 KB Output is correct
13 Correct 277 ms 31992 KB Output is correct
14 Correct 265 ms 32120 KB Output is correct
15 Correct 217 ms 32052 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 31992 KB Output is correct
2 Correct 256 ms 32008 KB Output is correct
3 Execution timed out 1082 ms 31992 KB Time limit exceeded
4 Halted 0 ms 0 KB -