oj.uz

Submission #1002073

# Submission time Handle Problem Language Result Execution time Memory
1002073 2024-06-19T09:41:38 Z 0pt1mus23 Watching (JOI13_watching) C++14
100 / 100
 50 ms 23364 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];
int vis[2000][2000];
int prec[2000][2];
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++;

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

        for(int i=0;i<n;i++){
            prec[i][0]=0;
            prec[i][1]=0;
            prec[i][0] = (--upper_bound(all(arr),arr[i]+w)) - arr.begin();
            prec[i][1] = (--upper_bound(all(arr),arr[i]+bigw)) - arr.begin();
        }
        for(int j=0;j<=min(n,p);j++){
            if(check){
                break;
            }
            for(int k=0;k<=min(n,q);k++){   
                if(check){
                    break;
                }
                if(vis[j][k]!=lg){
                    vis[j][k]=lg;
                    mx[j][k]=-1;
                }
                if(j || k){
                    if(j){
                        int y = mx[j-1][k];
                        int i = y+1;
                        // yeni p kullanicam
                        if(y>=i-1){
                            int yer = prec[i][0];
                            mx[j][k]= max(mx[j][k],yer);
                            tmx=max(tmx,mx[j][k]);
                            if(tmx>=n-1){
                                check=true;
                                break;
                            }
                        }
                    }
                    if(k){
                        int y = mx[j][k-1];
                        int i = y+1;
                        if(y>=i-1){
                            int yer = prec[i][1];
                            mx[j][k]=max(mx[j][k],yer);
                            tmx=max(tmx,mx[j][k]);
                            if(tmx>=n-1){
                                check=true;
                                break;
                            }
                        }
                    }
                }
            }
        }
    
        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 0 ms 396 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 972 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 0 ms 348 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 2 ms 544 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 22 ms 15464 KB Output is correct
4 Correct 17 ms 18012 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 7 ms 3008 KB Output is correct
9 Correct 12 ms 7904 KB Output is correct
10 Correct 22 ms 18608 KB Output is correct
11 Correct 7 ms 3100 KB Output is correct
12 Correct 50 ms 23364 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 4 ms 700 KB Output is correct
15 Correct 5 ms 616 KB Output is correct