Submission #524368

#	Time	Username	Problem	Language	Result	Execution time	Memory
524368		CPSC	Group Photo (JOI21_ho_t3)	C++14	100 / 100	914 ms	134504 KiB

Main

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 5005;
int n,a[N],idx[N],dp1[N][N],dp2[N][N],dp[N];
int tree[N];
void update(int idx, int val) {
    for (int i = idx; i < N; i+=i&(-i)) {
        tree[i] += val;
    }
}
int getans(int le, int ri) {
    int pas = 0;
    for (int i = ri; i > 0; i-=i&(-i)) {
        pas += tree[i];
    }
    for (int i = le - 1; i > 0; i-=i&(-i)){
        pas -= tree[i];
    }
    return pas;
}
main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        idx[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        update(idx[i],1);
        for (int j = i + 1; j <= n; j++) {
            dp1[i][j] = dp1[i][j - 1] + getans(idx[j],n);
        }
    }
    for (int i = 1; i < N; i++) tree[i] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            dp2[i][j] = dp2[i][j - 1] + getans(1, idx[j] - 1);
            update(idx[j],1);
        }
        for (int j = i; j <= n; j++) {
            update(idx[j], -1);
        }
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e9;
        for (int j = i - 1; j >= 0; j--) {
            // j ---> 1   +  i ---> j + 1
            dp[i] = min(dp[i],dp[j] + dp1[j][i] + dp2[j + 1][i]);
        }
    }
    cout<<dp[n]<<endl;
}

Compilation message (stderr)

Main.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main() {
      | ^~~~

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