Submission #766002

#	Time	Username	Problem	Language	Result	Execution time	Memory
766002		pandapythoner	Financial Report (JOI21_financial)	C++14	48 / 100	4072 ms	16228 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

int n, d;
vector<ll> a;
vector<int> go;

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> d;
    a.resize(n);
    for (int i = 0; i < n; i += 1) {
        cin >> a[i];
    }
    go.resize(n);
    set<pair<int, int>> sgs;
    vector<pair<ll, int>> srtd(n);
    for (int i = 0; i < n; i += 1) {
        srtd[i] = make_pair(a[i], i);
    }
    sort(all(srtd), [](const pair<ll, int> &a, const pair<ll, int> &b) {
        if (a.first != b.first) {
            return a.first < b.first;
        }
        return a.second > b.second;
    });
    vector<int> dp(n, 0);
    int mx_dp = 0;
    for (auto [x, i] : srtd) {
        int r = i;
        int l = max(0, i - d);
        auto it = sgs.upper_bound(make_pair(l, l - 1));
        if (it != sgs.begin()) {
            auto pit = prev(it);
            if (pit->second >= l) {
                l = min(l, pit->first);
                r = max(r, pit->second);
                sgs.erase(pit);
            }
        }
        if (it != sgs.end() && it->first <= r) {
            r = max(r, it->second);
            l = min(l, it->first);
            sgs.erase(it);
        }
        sgs.insert(make_pair(l, r));
        int t = l;
        int mx = 0;
        for (int j = l; j < i; j += 1) {
            mx = max(mx, dp[j]);
        }
        dp[i] = mx + 1;
        mx_dp = max(mx_dp, dp[i]);
    }
    cout << mx_dp << "\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:39:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for (auto [x, i] : srtd) {
      |               ^
Main.cpp:57:13: warning: unused variable 't' [-Wunused-variable]
   57 |         int t = l;
      |             ^

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35