oj.uz

답안 #964270

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964270 2024-04-16T14:03:23 Z Unforgettablepl 구경하기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 63140 KB Output isn't correct
2 Halted 0 ms 0 KB -