제출 #1001892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001892		vjudge1	구경하기 (JOI13_watching)	C++14	0 / 100	1094 ms	672 KiB

watching

#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;
};


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 = 1e18;
    int ans=r;
    while(l<=r){

        int mid = (l+r)/2;
        int w = mid-1;
        int bigw = mid*2 -1;
        bool check=false;
    // int w = 4;
    // int bigw = 8;

    //     /*

    //         burdan sonrasi dp olaraq yazim?
    //             i ci yere boyuk qoysam, 
    //     */

        vector<vector<node>> dp(n,vector<node>(3,{-1,-1,-1}));
        // int w =4 ;
        int mxg = (--upper_bound(all(arr),arr[0] + w)) - arr.begin();
        int mxg2 = (--upper_bound(all(arr),arr[0] + bigw)) - arr.begin();
        // cout<<mxg<<endl;
        dp[0][1] = {p-1,q,mxg}; // 0 use small camera, 1 use big
        dp[0][2] = {p,q-1,mxg2}; // 0 use small camera, 1 use big

        if(mxg>=n-1 || mxg2>=n-1){
            check=true;
        }
        else{
            for(int i =1;i<n;i++){
                // i  ciye 0 qoysaq, yada 1 qoysaq ? qoya bilriik  hec?
                node gelen_enazp = {-1,-1,-1};
                node gelen_enazq = {-1,-1,-1};
                int mxa =-1;
                int mxb =-1;
                for(int j=0;j<i;j++){
                    if(dp[j][1].maxgedir>=i-1){
                        int qalan  =dp[j][1].qalanbalaca*(w+1) + dp[j][1].qalanboyuk*(bigw+1);
                        if(qalan >= gelen_enazp.qalanbalaca*(w+1) + gelen_enazp.qalanboyuk*(bigw+1)){
                            
                            if(dp[j][1].qalanbalaca){
                                gelen_enazp = dp[j][1];
                                mxa = (--upper_bound(all(arr),arr[i] + w) - arr.begin());
                            }
                        }
                    }
                    else{
                        int x = (dp[j][1].qalanbalaca ? (--upper_bound(all(arr),arr[dp[j][1].maxgedir+1] + w) - arr.begin()) : -1);
                        if(x>=i){
                            int qalan  =dp[j][1].qalanbalaca*(w+1) + dp[j][1].qalanboyuk*(bigw+1);
                            if(qalan >= gelen_enazp.qalanbalaca*(w+1) + gelen_enazp.qalanboyuk*(bigw+1)){
                                
                                if(dp[j][1].qalanbalaca){
                                    gelen_enazp = dp[j][1];
                                    mxa = x;
                                }
                            }
                        }
                    }

                    if(dp[j][2].maxgedir>=i-1){

                        int qalan = dp[j][2].qalanbalaca*(w+1) + dp[j][2].qalanboyuk*(bigw+1);
                        if(qalan >= gelen_enazp.qalanbalaca*(w+1) + gelen_enazp.qalanboyuk*(bigw+1)){
                            
                            if(dp[j][2].qalanbalaca){
                                gelen_enazp = dp[j][2];
                                mxa = (--upper_bound(all(arr),arr[i] + w) - arr.begin());
                            }
                        }
                    }
                    else{
                        int x = (dp[j][2].qalanbalaca ? (--upper_bound(all(arr),arr[dp[j][2].maxgedir+1] + w) - arr.begin()) : -1);
                        if(x>=i){
                            int qalan  =dp[j][2].qalanbalaca*(w+1) + dp[j][2].qalanboyuk*(bigw+1);
                            if(qalan >= gelen_enazp.qalanbalaca*(w+1) + gelen_enazp.qalanboyuk*(bigw+1)){
                                
                                if(dp[j][2].qalanbalaca){
                                    gelen_enazp = dp[j][2];
                                    mxa = x;
                                }
                            }
                        }
                    }


                    if(dp[j][1].maxgedir>=i-1){

                        int qalan  =dp[j][1].qalanbalaca*(w+1) + dp[j][1].qalanboyuk*(bigw+1);
                        if(qalan >= gelen_enazq.qalanbalaca*(w+1) + gelen_enazq.qalanboyuk*(bigw+1)){
                            if(dp[j][1].qalanboyuk){
                                gelen_enazq = dp[j][1];
                                mxb = (--upper_bound(all(arr),arr[i] + bigw) - arr.begin());
                            }
                        }
                    }
                    else{
                        int x = (dp[j][1].qalanboyuk ? (--upper_bound(all(arr),arr[dp[j][1].maxgedir+1] + bigw) - arr.begin()) : -1);
                        if(x>=i){

                            int qalan  =dp[j][1].qalanbalaca*(w+1) + dp[j][1].qalanboyuk*(bigw+1);
                            if(qalan >= gelen_enazq.qalanbalaca*(w+1) + gelen_enazq.qalanboyuk*(bigw+1)){
                                if(dp[j][1].qalanboyuk){
                                    gelen_enazq = dp[j][1];
                                    mxb = x;
                                }
                            }
                        }
                    }

                    if(dp[j][2].maxgedir>=i-1){

                        int qalan = dp[j][2].qalanbalaca*(w+1) + dp[j][2].qalanboyuk*(bigw+1);
                        if(qalan >= gelen_enazq.qalanbalaca*(w+1) + gelen_enazq.qalanboyuk*(bigw+1)){
                            if(dp[j][2].qalanboyuk){
                                gelen_enazq = dp[j][2];
                                mxb = (--upper_bound(all(arr),arr[i] + bigw) - arr.begin());
                            }
                        }
                    }
                    else{
                        int x = (dp[j][2].qalanboyuk ? (--upper_bound(all(arr),arr[dp[j][2].maxgedir+1] + bigw) - arr.begin()) : -1);
                        if(x>=i){

                            int qalan = dp[j][2].qalanbalaca*(w+1) + dp[j][2].qalanboyuk*(bigw+1);
                            if(qalan >= gelen_enazq.qalanbalaca*(w+1) + gelen_enazq.qalanboyuk*(bigw+1)){
                                if(dp[j][2].qalanboyuk){
                                    gelen_enazq = dp[j][2];
                                    mxb=x;
                                }
                            }
                        }
                    }
                }

                /*
                    optimallari goturduk, istifade vaxti
                */

                if(gelen_enazp.qalanbalaca>0){
                    int mxgedir = mxa;
                    gelen_enazp.qalanbalaca -= 1;
                    gelen_enazp.maxgedir = mxgedir;
                }
                
                if(gelen_enazq.qalanboyuk>0){
                    int mxgedir = mxb;
                    gelen_enazq.qalanboyuk -= 1;
                    gelen_enazq.maxgedir = mxgedir;
                    
                }

                dp[i][1] = gelen_enazp;
                dp[i][2] = gelen_enazq;
                if(dp[i][1].maxgedir>=n-1 || dp[i][2].maxgedir>=n-1){
                    // cout<<mid<<":ans "<<i<<"ciyer "<<dp[i][1].maxgedir<<" : "<<dp[i][2].maxgedir<<endl;
                    check=true;
                    break;
                }
            }

    // cout<<dp[1][1].maxgedir<<" "<<dp[1][2].maxgedir<<endl;

        }

        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: 0 / 50
• Subtask 2: 0 / 50