oj.uz

Submission #138158

# Submission time Handle Problem Language Result Execution time Memory
138158 2019-07-29T13:31:43 Z rzbt Watching (JOI13_watching) C++14
100 / 100
 477 ms 31992 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 2005
typedef long long ll;

using namespace std;

ll n,p,q;
ll niz[MAXN];
ll dp[MAXN][MAXN];
bool provera(ll w){
    for(ll i=0;i<MAXN;i++){
        for(ll j=0;j<MAXN;j++){
            dp[i][j]=10000000;
        }
    }
    for(ll j=0;j<MAXN;j++){
        dp[0][j]=0;
    }
    ll prosli=0,dprosli=0;
    for(ll i=1;i<=n;i++){
        while(niz[i]-niz[prosli+1]>=w)prosli++;
        while(niz[i]-niz[dprosli+1]>=w+w)dprosli++;

        dp[i][0]=1+dp[prosli][0];
        for(ll j=1;j<=n;j++){
            dp[i][j]=min(dp[dprosli][j-1],1+dp[prosli][j]);

        }
    }
    if(dp[n][q]<=p)return true;
    return false;

}

ll binarna(ll l,ll d,ll sol){
    if(l>d)return sol;
    ll mid=(l+d)/2;
    if(provera(mid))return binarna(l,mid-1,mid);
    return binarna(mid+1,d,sol);
}



int main()
{
    scanf("%lld %lld %lld", &n, &p, &q);
    for(ll i=1;i<=n;i++)scanf("%lld",niz+i);
    sort(niz+1,niz+n+1);

    p=min(p,n);
    q=min(q,n);

    printf("%lld",binarna(1,1e9+7,0));
    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &n, &p, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:52:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(ll i=1;i<=n;i++)scanf("%lld",niz+i);
                         ~~~~~^~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 31864 KB Output is correct
2 Correct 167 ms 31868 KB Output is correct
3 Correct 173 ms 31928 KB Output is correct
4 Correct 173 ms 31836 KB Output is correct
5 Correct 169 ms 31836 KB Output is correct
6 Correct 164 ms 31836 KB Output is correct
7 Correct 174 ms 31836 KB Output is correct
8 Correct 178 ms 31868 KB Output is correct
9 Correct 217 ms 31864 KB Output is correct
10 Correct 244 ms 31864 KB Output is correct
11 Correct 223 ms 31864 KB Output is correct
12 Correct 181 ms 31868 KB Output is correct
13 Correct 179 ms 31828 KB Output is correct
14 Correct 173 ms 31736 KB Output is correct
15 Correct 181 ms 31864 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 31864 KB Output is correct
2 Correct 169 ms 31832 KB Output is correct
3 Correct 378 ms 31864 KB Output is correct
4 Correct 396 ms 31856 KB Output is correct
5 Correct 384 ms 31864 KB Output is correct
6 Correct 368 ms 31964 KB Output is correct
7 Correct 373 ms 31964 KB Output is correct
8 Correct 376 ms 31864 KB Output is correct
9 Correct 368 ms 31856 KB Output is correct
10 Correct 361 ms 31992 KB Output is correct
11 Correct 360 ms 31964 KB Output is correct
12 Correct 362 ms 31872 KB Output is correct
13 Correct 385 ms 31864 KB Output is correct
14 Correct 387 ms 31860 KB Output is correct
15 Correct 394 ms 31860 KB Output is correct