Submission #569084

#	Time	Username	Problem	Language	Result	Execution time	Memory
569084		dantoh000	Group Photo (JOI21_ho_t3)	C++14	100 / 100	591 ms	117664 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[5005];
int pos[5005];
int cost[5005][5005];
int fw[5005];
int fw2[5005];
int dp[5005];

void up(int *f, int x){
    while (x <= n){
        f[x]++;
        x += x&-x;
    }
}
int qu(int *f, int x){
    int ret = 0;
    while (x){
        ret += f[x];
        x -= x&-x;
    }
    return ret;
}
main(){
    scanf("%lld",&n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld",&a[i]);
        pos[a[i]] = i;
    }
    for (int i = 1; i <= n; i++){
        int pos1 = 0;
        int pos2 = 0;
        for (int j = 1; j <= n; j++){
            fw[j] = 0;
        }
        int num_inv = 0;
        for (int j = i; j <= n; j++){
            int realpos = pos[j] + (i-1)-qu(fw2, pos[j]);
            pos1 += realpos;
            pos2 += j;
            num_inv += qu(fw, pos[j]);
            cost[i][j] = pos1-pos2 + num_inv;
            ///printf("cost %lld %lld = %lld (realpos = %lld, pos = %lld)\n",i,j,cost[i][j],realpos, j);
            up(fw,pos[j]);
        }
        up(fw2, pos[i]);
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++){
        dp[i] = 1000000000000000000;
        for (int j = 1; j <= i; j++){
            ///printf("dp[%lld] = %lld, + %lld\n",j-1,dp[j-1],cost[j][i]);
            dp[i] = min(dp[i], dp[j-1]+cost[j][i]);
        }
        ///printf("dp[%lld] = %lld\n",i,dp[i]);

    }
    printf("%lld",dp[n]);



}

Compilation message (stderr)

Main.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
Main.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~

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