Submission #237370

#	Time	Username	Problem	Language	Result	Execution time	Memory
237370		uacoder123	Watching (JOI13_watching)	C++14	50 / 100	1089 ms	16504 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
lli s,l;
vi v;
int dp[2001][2001];
int cal(int p,int s1,int w)
{
    if(dp[p][s1]!=-1)
        return(dp[p][s1]);
    if(p==v.size())
        return(0);
    int i1=lower_bound(all(v),w+v[p])-v.begin(),i2=lower_bound(all(v),2*w+v[p])-v.begin();
    if(s1>0)
        dp[p][s1]=min(cal(i1,s1-1,w),1+cal(i2,s1,w));
    else
        dp[p][s1]=1+cal(i2,s1,w);
    return(dp[p][s1]);
}
lli check(lli w)
{
    memset(dp,-1,sizeof(dp));
    return((cal(0,s,w)<=l)?1:0);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli test=1;
    for(;test>0;--test)
    {
        lli n,f,ans=1000000000,le=1,ri=1000000002;
        cin>>n>>s>>l;
        for(lli i=0;i<n;++i)
        {
            cin>>f;
            v.pb(f);
        }
        sort(all(v));
        if(s+l>=n)
        {
            cout<<1<<endl;
            exit(0);
        }
        while(le<=ri)
        {
            lli m=(le+ri)/2;
            if(check(m))
            {
                ans=m;
                ri=m-1;
            }
            else
                le=m+1;
        }
        cout<<ans<<endl;
    }
    return(0);
} 

Compilation message (stderr)

watching.cpp: In function 'int cal(int, int, int)':
watching.cpp:24:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p==v.size())
        ~^~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50