oj.uz

Submission #964219

# Submission time Handle Problem Language Result Execution time Memory
964219 2024-04-16T12:32:12 Z Unforgettablepl Watching (JOI13_watching) C++17
50 / 100
 75 ms 33152 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef long long ll;

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

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


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 40 ms 16564 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 38 ms 16588 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 42 ms 16472 KB Output is correct
8 Correct 41 ms 16476 KB Output is correct
9 Correct 43 ms 16540 KB Output is correct
10 Correct 60 ms 16472 KB Output is correct
11 Correct 47 ms 16564 KB Output is correct
12 Correct 75 ms 16568 KB Output is correct
13 Correct 46 ms 16564 KB Output is correct
14 Correct 36 ms 16472 KB Output is correct
15 Correct 40 ms 16472 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 33152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -