Submission #1001567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001567		vjudge1	Watching (JOI13_watching)	C++14	0 / 100	148 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 = 1e9+1;
    int ans=1e9+1;
    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};
                for(int j=0;j<i;j++){
                    if(dp[j][1].maxgedir>=i-1){
                        int qalan  =dp[j][1].qalanbalaca*w + dp[j][1].qalanboyuk*bigw;
                        if(qalan >= gelen_enazp.qalanbalaca*w + gelen_enazp.qalanboyuk*bigw){
                            
                            if(dp[j][1].qalanbalaca){
                                gelen_enazp = dp[j][1];
                            }
                        }
                        if(qalan >= gelen_enazq.qalanbalaca*w + gelen_enazq.qalanboyuk*bigw){
                            if(dp[j][1].qalanboyuk){
                                gelen_enazq = dp[j][1];
                            }
                        }
                    }

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

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

                /*
                    optimallari goturduk, istifade vaxti
                */

                if(gelen_enazp.qalanbalaca>0){
                    int mxgedir = (--upper_bound(all(arr),arr[i] + w)) - arr.begin();
                    gelen_enazp.qalanbalaca -= 1;
                    gelen_enazp.maxgedir = mxgedir;
                }
                
                if(gelen_enazq.qalanboyuk>0){
                    int mxgedir = (--upper_bound(all(arr),arr[i] + bigw)) - arr.begin();
                    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<<w<<" "<<i<<" "<<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