oj.uz

Submission #538748

# Submission time Handle Problem Language Result Execution time Memory
538748 2022-03-17T16:37:08 Z __Variatto Watching (JOI13_watching) C++17
100 / 100
 342 ms 16088 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 712 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 712 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 712 KB Output is correct
15 Correct 1 ms 712 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 16084 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 264 ms 16080 KB Output is correct
4 Correct 84 ms 16084 KB Output is correct
5 Correct 294 ms 16084 KB Output is correct
6 Correct 342 ms 16088 KB Output is correct
7 Correct 79 ms 16088 KB Output is correct
8 Correct 171 ms 16084 KB Output is correct
9 Correct 99 ms 16084 KB Output is correct
10 Correct 88 ms 16084 KB Output is correct
11 Correct 290 ms 16088 KB Output is correct
12 Correct 202 ms 16084 KB Output is correct
13 Correct 83 ms 16072 KB Output is correct
14 Correct 82 ms 16040 KB Output is correct
15 Correct 76 ms 16084 KB Output is correct