oj.uz

Submission #766552

# Submission time Handle Problem Language Result Execution time Memory
766552 2023-06-25T21:13:54 Z Essa2006 Watching (JOI13_watching) C++14
100 / 100
 314 ms 15368 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int inf=1e9;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, p, q;
    cin>>n>>p>>q;
    if(q+p>=n)
        return cout<<1, 0;
    // p -> w
    // q -> 2*w
    vector<int>A(n);
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    sort(all(A));
    int l=0, r=1e9, ans;
    while(l<=r){
        int md=(l+r)/2;
        vector<vector<int>>Mn(n, vector<int>(q+1, inf));
        for(int i=0;i<n;i++){
            int fir2=-1, fir1=-1;
            for(int j=i;j>=0;j--){
                if(A[i]-A[j]+1>2*md){
                    fir2=j;
                    break;
                }
            }
            for(int j=i;j>=0;j--){
                if(A[i]-A[j]+1>md){
                    fir1=j;
                    break;
                }
            }
            Mn[i][0]=(fir1==-1?0:Mn[fir1][0])+1;
            for(int j=1;j<=q;j++){
                Mn[i][j]=min({Mn[i][j], (fir2==-1?0:Mn[fir2][j-1]), (fir1==-1?0:Mn[fir1][j])+1});
            }
        }
        int mn=inf;
        for(int i=0;i<=q;i++){
            mn=min(mn, Mn[n-1][i]);
        }
        if(mn<=p)
            ans=md, r=md-1;
        else
            l=md+1;
    }
    cout<<ans;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:55:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     cout<<ans;
      |           ^~~

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 440 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 21 ms 468 KB Output is correct
8 Correct 123 ms 6352 KB Output is correct
9 Correct 27 ms 1392 KB Output is correct
10 Correct 30 ms 1104 KB Output is correct
11 Correct 314 ms 15368 KB Output is correct
12 Correct 155 ms 8188 KB Output is correct
13 Correct 24 ms 468 KB Output is correct
14 Correct 18 ms 468 KB Output is correct
15 Correct 16 ms 560 KB Output is correct