Submission #538748

#	Time	Username	Problem	Language	Result	Execution time	Memory
538748		__Variatto	Watching (JOI13_watching)	C++17	100 / 100	342 ms	16088 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e3+10, MAXV=1e9+10;;
int n, s, l, t[MAX], dp[MAX][MAX];
bool spr(int w){
    for(int i=1; i<=n; i++)
        for(int j=0; j<=n; j++)
            dp[i][j]=MAXV;
    int ostw=0, ost2w=0;
    for(int i=1; i<=n; i++){
        if(t[i]-t[ostw]+1>w){
        while(t[i]-t[ostw]+1>w)
                ostw++;
            ostw--;
        }
        if(t[i]-t[ost2w]+1>2*w){
            while(t[i]-t[ost2w]+1>2*w)
                ost2w++;
            ost2w--;
        }
        for(int j=0; j<=l; j++){
            if(ostw)
                dp[i][j]=min(dp[i][j], dp[ostw][j]+1);
            else 
                dp[i][j]=min(dp[i][j], 1);
            if(j>0){
                if(ost2w)
                    dp[i][j]=min(dp[i][j], dp[ost2w][j-1]);
                else
                    dp[i][j]=0;
            }
        }
    }
    return (dp[n][l]<=s);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>s>>l;
    s=min(n, s), l=min(l, n);
    for(int i=1; i<=n; i++)
        cin>>t[i];
    sort(t+1, t+n+1);
    int pocz=1, kon=MAXV, sr, wyn=0;
    while(pocz<=kon){
        sr=(pocz+kon)/2;
        if(spr(sr))
            kon=sr-1, wyn=sr;
        else
            pocz=sr+1;
    }
    cout<<wyn<<"\n";
}

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