oj.uz

Submission #1114760

# Submission time Handle Problem Language Result Execution time Memory
1114760 2024-11-19T14:40:05 Z Newtonabc Watching (JOI13_watching) C++14
100 / 100
 708 ms 16208 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int dp[N][N],arr[N];
int main(){
    int n,p,q;
    cin>>n >>p >>q;
    for(int i=1;i<=n;i++) cin>>arr[i];
    arr[n+1]=INT_MAX;
    sort(arr+1,arr+n+1);
    int l=0,r=1e9;
    p=min(p,n),q=min(q,n);
    while(l<r){
        int w=(l+r)/2;
        for(int i=0;i<=p;i++) for(int j=0;j<=q;j++) dp[i][j]=0;
        for(int i=0;i<=p;i++){
            for(int j=0;j<=q;j++){
                if(i) dp[i][j]=max(dp[i][j],dp[i-1][j]);
                if(j) dp[i][j]=max(dp[i][j],dp[i][j-1]);
                if(dp[i][j]==n) continue;
                if(i) dp[i][j]=max(dp[i][j],dp[i-1][j]+(int)(upper_bound(arr+dp[i-1][j]+1,arr+n+2,w+arr[dp[i-1][j]+1]-1)-(arr+dp[i-1][j]+1)));
                if(j) dp[i][j]=max(dp[i][j],dp[i][j-1]+(int)(upper_bound(arr+dp[i][j-1]+1,arr+n+2,2*w+arr[dp[i][j-1]+1]-1)-(arr+dp[i][j-1]+1)));
            }
        }
        if(dp[p][q]==n) r=w;
        else l=w+1;
        /*cout<<w <<"\n";
        for(int i=0;i<=p;i++){
            for(int j=0;j<=q;j++){
                cout<<dp[i][j] <<" ";
            }
            cout<<"\n";
        }*/
    }
    cout<<l;
    
    
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 2504 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 520 ms 12880 KB Output is correct
4 Correct 54 ms 15440 KB Output is correct
5 Correct 48 ms 2640 KB Output is correct
6 Correct 708 ms 16208 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 42 ms 2676 KB Output is correct
9 Correct 52 ms 6736 KB Output is correct
10 Correct 62 ms 15064 KB Output is correct
11 Correct 56 ms 2808 KB Output is correct
12 Correct 314 ms 8840 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct