oj.uz

Submission #964272

# Submission time Handle Problem Language Result Execution time Memory
964272 2024-04-16T14:03:52 Z Unforgettablepl Watching (JOI13_watching) C++17
100 / 100
 487 ms 63320 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef long long ll;

pair<int,int> DP[2001][2001];
int arr[2001];
int n,p,q;

bool check(int w){
    for(auto&i:DP)for(auto&j:i)j={-1e15,0ll};
    for(auto&i:DP[0])i.first=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=q;j++){
            if(DP[i-1][j].second>=arr[i])DP[i][j]=DP[i-1][j];
            if(j!=0)DP[i][j]=max(DP[i][j],{DP[i-1][j-1].first,arr[i]+w-1});
            DP[i][j]=max(DP[i][j],{DP[i-1][j].first-1,arr[i]+2*w-1});
        }
    }
    return -DP[n][q].first > p;
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q >> p;
    for(int i=1;i<=n;i++)cin>>arr[i];
    if(p+q>=n){
        cout << "1\n";
        return 0;
    }
    sort(arr+1,arr+1+n);
    int ans = 0;
    for(int jump=536870912;jump;jump/=2){
        if(check(ans+jump))ans+=jump;
    }
    ans++;
    cout << ans << '\n';
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 63120 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 169 ms 63116 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 171 ms 63140 KB Output is correct
8 Correct 177 ms 63120 KB Output is correct
9 Correct 166 ms 63120 KB Output is correct
10 Correct 167 ms 63116 KB Output is correct
11 Correct 168 ms 63064 KB Output is correct
12 Correct 167 ms 63068 KB Output is correct
13 Correct 169 ms 63120 KB Output is correct
14 Correct 174 ms 63116 KB Output is correct
15 Correct 165 ms 63320 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 63136 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 476 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 179 ms 63168 KB Output is correct
8 Correct 202 ms 63156 KB Output is correct
9 Correct 318 ms 63156 KB Output is correct
10 Correct 487 ms 63160 KB Output is correct
11 Correct 193 ms 63064 KB Output is correct
12 Correct 344 ms 63156 KB Output is correct
13 Correct 184 ms 63152 KB Output is correct
14 Correct 184 ms 63068 KB Output is correct
15 Correct 184 ms 63168 KB Output is correct