Submission #138158

#	Time	Username	Problem	Language	Result	Execution time	Memory
138158		rzbt	Watching (JOI13_watching)	C++14	100 / 100	477 ms	31992 KiB

watching

#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 (stderr)

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 / 50
• Subtask 2: 50 / 50