Submission #388176

#	Time	Username	Problem	Language	Result	Execution time	Memory
388176		BartolM	Group Photo (JOI21_ho_t3)	C++17	100 / 100	860 ms	524 KiB

Main

#define DEBUG 1
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=5005;

struct Fenwick{
    int F[N];
    Fenwick() {
        memset(F, 0, sizeof F);
    }
    int query(int x) {
        int ret=0;
        for (x++; x>0; x-=x&-x) ret+=F[x];
        return ret;
    }
    void update(int x, int val) {
        for (x++; x<N; x+=x&-x) F[x]+=val;
    }
    void reset() {
        memset(F, 0, sizeof F);
    }

};

int n;
int p[N], pos[N];
int dp[N];
Fenwick F1, F2;

void solve() {
    dp[n+1]=0;
    for (int i=n; i>0; --i) {
        dp[i]=INF;
        F1.reset(); F2.reset();
        for (int j=i; j<=n; ++j) F1.update(pos[j], 1);
        int dod=0;
        for (int j=i; j<=n; ++j) {
            dod+=F1.query(pos[j]-1)-(F2.query(n)-F2.query(pos[j]));
            dp[i]=min(dp[i], dp[j+1]+dod);
            F2.update(pos[j], 1);
        }
    }
    printf("%d\n", dp[1]);
}

void load() {
    scanf("%d", &n);
    for (int i=1; i<=n; ++i) {
        scanf("%d", &p[i]);
        pos[p[i]]=i;
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void load()':
Main.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |         scanf("%d", &p[i]);
      |         ~~~~~^~~~~~~~~~~~~

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