Submission #421661

#	Time	Username	Problem	Language	Result	Execution time	Memory
421661		Aldas25	Exam (eJOI20_exam)	C++14	65 / 100	805 ms	429552 KiB

exam

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;

const int MAXN = 500100;
const ll INF = 1e16;
const ll MOD = 1e9+7;

set<int> cur;
map<int, int> toId;

int n;
int a[MAXN], b[MAXN];
int pref[5100][2*5100];
int dp[MAXN];

void compress () {
    FOR(i ,1, n) {
        cur.insert(a[i]);
        cur.insert(b[i]);
    }

    int curId = 0;
    for (int x : cur) {
        toId[x] = ++curId;
    }

    FOR(i, 1, n) {
        a[i] = toId[a[i]];
        b[i] = toId[b[i]];
    }
}

void precPref () {
    FOR(i, 1, n) {
        FOR(j, 0, 2*n+5) pref[i][j] = pref[i-1][j];
        pref[i][b[i]]++;
    }
}

int cnt (int k, int fr, int to) {
    return pref[to][k] - pref[fr-1][k];
}

int main()
{
    FAST_IO;

    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) cin >> b[i];

    compress();
    precPref();

    int ans = 0;
    FOR(i,1 , n) {
        int fr = i, to = i;
        while (fr > 1 && a[fr-1] <= a[i]) {fr--;}
        while (to < n && a[to+1] <= a[i]) {to++;}

        int mx = dp[fr-1] - pref[fr-1][a[i]];
        FOR(y, fr, to) {
            dp[y] = max(dp[y], pref[y][a[i]] + mx);
            //cout << " count of " << a[i] << " in [" << x << "; " << y << "] = " << cnt(a[i], x, y) << endl;
            //cout << " i = " << i << " x = " << x << " y = " << y << " dp y = " << dp[y] << endl;
            ans = max(ans, dp[y]);
            mx = max(mx, dp[y] - pref[y][a[i]]);
        }
    }

    cout << ans << "\n";

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 12
• Subtask 3: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22