oj.uz

Submission #964270

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

#define int long long
typedef long long ll;

pair<int,int> DP[2001][2001];
int arr[101];
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 177 ms 63064 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 169 ms 63324 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 168 ms 63120 KB Output is correct
8 Correct 180 ms 63120 KB Output is correct
9 Correct 173 ms 63124 KB Output is correct
10 Correct 172 ms 63068 KB Output is correct
11 Correct 170 ms 63312 KB Output is correct
12 Correct 179 ms 63120 KB Output is correct
13 Correct 169 ms 63064 KB Output is correct
14 Correct 168 ms 63068 KB Output is correct
15 Correct 175 ms 63368 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 63140 KB Output isn't correct
2 Halted 0 ms 0 KB -