Submission #378383

#	Time	Username	Problem	Language	Result	Execution time	Memory
378383		smjleo	Group Photo (JOI21_ho_t3)	C++14	100 / 100	1161 ms	856 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1000000007, mod2 = 998244353;

// change this
const int N = 5005;

int n, h[N], fw[N], fw2[N], pos[N], dp[N];

void update(int x, int v) {
    for (; x<N; x+=x&(-x)) fw[x] += v; 
}
int sum(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}

void update2(int x, int v) {
    for (; x<N; x+=x&(-x)) fw2[x] += v; 
}

int sum2(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw2[x];
    return res;
}

signed main() {
    io;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> h[i];
        pos[h[i]] = i;
    }

    for (int i=1; i<=n; i++) {
        dp[i] = 1e18;

        int ans = 0;
        for (int j=1; j<=i; j++) {
            ans += sum(pos[j] - 1);
            update(pos[j], 1);
        }
        memset(fw2, 0, sizeof fw2);
        for (int j=0; j<i; j++) {
            // find dp
            dp[i] = min(dp[i], dp[j] + ans);
            // remove
            ans -= sum(n) - sum(pos[j+1]);
            ans -= sum2(n) - sum2(pos[j+1]);
            update(pos[j+1], -1);
            // add
            ans += sum(pos[j+1]);
            update2(pos[j+1], 1);
        }
    }

    cout << dp[n] << nl;
}   

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36