Submission #887252

#	Time	Username	Problem	Language	Result	Execution time	Memory
887252		_minhduc	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	53 ms	23252 KiB

prison

#include <bits/stdc++.h>
#define int long long
#define ii pair <int, int>
#define task "playdom"

using namespace std;
const int maxn = 2e6 + 5;

int n, D, T, t[maxn];

namespace ac {
    int sum[maxn], dd[maxn];

    void solve() {
        int ma = 0;
        priority_queue <ii, vector <ii>, greater <ii>> pq;

        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + (t[i] > T);

        for (int i = 1; i <= n; i++)
            if (t[i] <= T)
                ma = max (ma, T - t[i] + i);
            else {
                if (ma >= i)
                    if (pq.size() < D)
                        pq.push({sum[ma] - sum[i - 1], i});
                    else {
                        pq.push({sum[ma] - sum[i - 1], i});
                        pq.pop();
                    }
                ma = 0;
            }

        while (pq.size()) {
            dd[pq.top().second] = 1;
            pq.pop();
        }

        int res = n;
        for (int i = 1; i <= n; i++)
            if (t[i] <= T)
                ma = max (ma, T - t[i] + i);
            else {
                if (dd[i] == 1) {
                    res--;
                    ma = 0;
                }
                else
                    if (ma < i) {
                        res--;
                        ma = 0;
                    }
            }

        cout << res;
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);

    cin >> n >> D >> T;
    for (int i = 1; i <= n; i++)
        cin >> t[i];

    ac::solve();
}

Compilation message (stderr)

prison.cpp: In function 'void ac::solve()':
prison.cpp:26: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]
   26 |                     if (pq.size() < D)
      |                         ~~~~~~~~~~^~~
prison.cpp:25:20: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   25 |                 if (ma >= i)
      |                    ^
prison.cpp: At global scope:
prison.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main() {
      | ^~~~

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