Submission #887250

#	Time	Username	Problem	Language	Result	Execution time	Memory
887250		_minhduc	The short shank; Redemption (BOI21_prison)	C++14	15 / 100	47 ms	18616 KiB

prison

/**
 *    author:       _minhduc
 *    created:      14-12-2023 13:30:37
**/

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define taskname ""

using namespace std;

const int maxN = (int)(2e6);

int n,d,a;
int arr[maxN+5];

namespace sub1 {
    const int N = (int)(500);

    int dp[N+5][N+5];

    void main() {
        for (int i = 0; i < n; i++)
            cin >> arr[i];
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= d+1; j++)
                dp[i][j] = (int)(1e16);
        dp[n][0] = 0;
        for (int i = n-1; i >= 0; i--) 
            for (int j = 1; j <= d+1; j++) {
                int cnt = 0, mn = arr[i];
                for (int k = i+1; k <= n; k++) {
                    cnt += (mn <= a);
                    dp[i][j] = min(dp[i][j],dp[k][j-1] + cnt);
                    mn = min(mn+1,arr[k]);
                }
            }
        cout << dp[0][d+1];
    }
}

namespace sub6 {
    int F[maxN+5],dd[maxN+5];
    void main() {
        int mx = 0;
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        for (int i = 1; i <= n; i++)
            cin >> arr[i];
        for (int i = 1; i <= n; i++)
            F[i] = F[i-1] + (arr[i] > a);
        for (int i = 1; i <= n; i++) 
            if (arr[i] < a)
                mx = max(mx,a-arr[i]+i);
            else {
                if (mx >= i) {
                    if (pq.size() < d) {
                        pq.push({F[mx] - F[i-1],i});
                    } else {
                        pq.push({F[mx] - F[i-1],i});
                        pq.pop();
                    }
                }
                mx = 0;
            }
        while (pq.size()) {
            dd[pq.top().second] = 1;
            pq.pop();
        }
        int res = n;
        for (int i = 1; i <= n; i++) 
            if (arr[i] < a)
                mx = max(mx,a-arr[i]+i);
            else {
                if (dd[i]) {
                    res--;
                    mx = 0;
                } else {
                    if (mx < i) {
                        res--;
                        mx = 0;
                    }
                }
            }
        cout << res;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    #ifdef ONLINE_JUDGE
        // freopen(taskname".inp", "r", stdin);
        // freopen(taskname".out", "w", stdout);
    #endif
    cin >> n >> d >> a;
    if (n <= 500)
        sub1::main();
    else 
        sub6::main();
}

Compilation message (stderr)

prison.cpp: In function 'void sub6::main()':
prison.cpp:57:35: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long long int, long long int>, std::vector<std::pair<long long int, long long int> >, std::greater<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   57 |                     if (pq.size() < d) {
      |                         ~~~~~~~~~~^~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20