oj.uz

Submission #939553

# Submission time Handle Problem Language Result Execution time Memory
939553 2024-03-06T13:50:14 Z JakobZorz Watching (JOI13_watching) C++17
100 / 100
 483 ms 16296 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

int n,p,q;
int arr[2000];
int nxt1[2001];
int nxt2[2001];

bool get(int w){
    nxt1[n]=n;
    nxt2[n]=n;
    for(int i=0;i<n;i++){
        nxt1[i]=i;
        while(nxt1[i]<n&&arr[nxt1[i]]<arr[i]+w)
            nxt1[i]++;
    }
    for(int i=0;i<n;i++){
        nxt2[i]=i;
        while(nxt2[i]<n&&arr[nxt2[i]]<arr[i]+2*w)
            nxt2[i]++;
    }
    vector<vector<int>>dp(p+1,vector<int>(q+1)); // dp[i1][i2] = how far can you come with using i1 small and i2 big cameras
    for(int i1=0;i1<=p;i1++){
        for(int i2=0;i2<=q;i2++){
            if(i1){
                dp[i1][i2]=max(dp[i1][i2],nxt1[dp[i1-1][i2]]);
            }
            if(i2){
                dp[i1][i2]=max(dp[i1][i2],nxt2[dp[i1][i2-1]]);
            }
        }
    }
    return dp[p][q]==n;
}

void solve(){
    cin>>n>>p>>q;
    p=min(n,p);
    q=min(n,q);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n);
    int l=0,r=1e9;
    while(l<r-1){
        int m=(l+r)/2;
        if(get(m))
            r=m;
        else
            l=m;
    }
    cout<<r<<"\n";
}

int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("/Users/jakob/cp_testing/test.txt","r",stdin);freopen("output.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

/*
3 1 1
2
11
17
 */

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 456 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 496 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 282 ms 9412 KB Output is correct
4 Correct 27 ms 1160 KB Output is correct
5 Correct 23 ms 1124 KB Output is correct
6 Correct 483 ms 16296 KB Output is correct
7 Correct 26 ms 348 KB Output is correct
8 Correct 18 ms 872 KB Output is correct
9 Correct 20 ms 896 KB Output is correct
10 Correct 27 ms 1224 KB Output is correct
11 Correct 24 ms 1168 KB Output is correct
12 Correct 125 ms 4320 KB Output is correct
13 Correct 19 ms 612 KB Output is correct
14 Correct 12 ms 488 KB Output is correct
15 Correct 13 ms 504 KB Output is correct