oj.uz

Submission #1001982

# Submission time Handle Problem Language Result Execution time Memory
1001982 2024-06-19T08:58:13 Z vjudge1 Watching (JOI13_watching) C++14
50 / 100
 1000 ms 31772 KB 
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
const int   prime = 23,inf = 2e18,mod = 1e9 +7,sze =1e6;

struct node{
    int qalanbalaca;
    int qalanboyuk;
    int maxgedir;
};

int mx[2000][2000];
void mal(){
    int n,p,q;
    cin>>n>>p>>q;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    sort(all(arr));
    int l = 1;
    int r = 1e9;
    int ans=r;
    int lg =0;
    while(l<=r){
        lg++;

    memset(mx, -1,sizeof mx);
        int mid = (l+r)/2;
        int w = mid-1;
        int bigw = mid*2 -1;
        bool check=false;
        int tmx =0;
        
        for(int j=0;j<=min(n,p);j++){
            for(int k=0;k<=min(n,q);k++){   
                if(j || k){
                    if(j){
                        int y = mx[j-1][k];
                        int i = y+1;
                        // yeni p kullanicam
                        if(y>=i-1){
                            int yer = (--upper_bound(all(arr),arr[i] + w)) - arr.begin();
                            mx[j][k]= max(mx[j][k],yer);
                            tmx=max(tmx,mx[j][k]);
                        }
                    }
                    if(k){
                        int y = mx[j][k-1];
                        int i = y+1;
                        if(y>=i-1){
                            int yer = (--upper_bound(all(arr),arr[i]+bigw)) - arr.begin();
                            mx[j][k]=max(mx[j][k],yer);
                            tmx=max(tmx,mx[j][k]);
                        }
                    }
                }
            }
        }
    
        if(tmx>=n-1){
            check=true;
        }
        
        /*
            i ci yere qeder j dene small, k dene big kullanildi
        */
 
        if(check){
            // cout<<mid<<" "<<w<<" "<<bigw<<endl;
            r=mid-1;
            ans=mid;
        }
        else{
            l=mid+1;
        }

    }
    drop(ans);
}   

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    
    while(tt--){
        mal();        
    }
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31580 KB Output is correct
2 Correct 43 ms 31580 KB Output is correct
3 Correct 49 ms 31580 KB Output is correct
4 Correct 43 ms 31576 KB Output is correct
5 Correct 45 ms 31576 KB Output is correct
6 Correct 58 ms 31580 KB Output is correct
7 Correct 43 ms 31580 KB Output is correct
8 Correct 42 ms 31576 KB Output is correct
9 Correct 45 ms 31576 KB Output is correct
10 Correct 46 ms 31576 KB Output is correct
11 Correct 51 ms 31580 KB Output is correct
12 Correct 45 ms 31772 KB Output is correct
13 Correct 42 ms 31512 KB Output is correct
14 Correct 43 ms 31576 KB Output is correct
15 Correct 45 ms 31752 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 31616 KB Output is correct
2 Correct 50 ms 31576 KB Output is correct
3 Execution timed out 1020 ms 31580 KB Time limit exceeded
4 Halted 0 ms 0 KB -