제출 #486969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486969		bigDuck	Group Photo (JOI21_ho_t3)	C++14	100 / 100	859 ms	117824 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
inline char get_ (){
    const int oo=1000005;
    static char buf[oo], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, oo, stdin), p1 == p2) ? EOF : *p1 ++;
}
int read_ () {
    char c = get_();
    int sum = 0;
    while(!(c >= '0' && c <= '9')) c = get_();
    while(c >= '0' && c <= '9') sum = sum * 10 + (c - '0'), c = get_();
    return sum;
}



int n, H[5001];
int dp[5001];
int fw[5001];




void update(int i, int x){

for(int j=i; j<=n; j+=(j&(-j))){
    fw[j]+=x;
}

}

int query(int i){
int res=0;
for(int j=i; j>0; j-=(j&(-j)) ){
    res+=fw[j];
}
return res;
}

int ord[5001];
int h[5001];
int c[5001][5001];


int32_t main(){
INIT
cin>>n;
for(int i=1; i<=n; i++){
    cin>>H[i];
    //ord[H[i] ]=i;
}

for(int i=1; i<=n; i++){
    for(int j=1; j<i; j++){
        h[j]=j;
    }
    for(int j=1, cnt=i; j<=n; j++){
        if(H[j]>=i){
            h[cnt]=H[j];
            ord[h[cnt] ]=cnt;
            cnt++;
        }
    }
    for(int j=1; j<=n; j++){
        fw[j]=0;
    }


    int mn1=0;
    for(int j=i; j<=n; j++){
        int add=ord[j]+query(ord[j])-j;
        mn1+=add;
        update(i, 1);
        update(ord[j]+1, -1);
        c[i][j]=mn1;
    }


    for(int j=1; j<=n; j++){
        fw[j]=0;
    }

    int mn2=0;
    for(int j=i; j<=n; j++){
        int add=ord[j]-i-(j-i-query(ord[j]) );
        mn2+=add;
        update(ord[j], 1);
        c[i][j]=min(c[i][j], mn2);
    }

}



for(int i=1; i<=n; i++){
    dp[i]=1e18;
    for(int j=i-1; j>=0; j--){
        dp[i]=min(dp[i], dp[j]+c[j+1][i]);
    }
}

/*
for(int i=1; i<=n; i++){
    cout<<dp[i]<<" ";
}
*/
cout<<dp[n];

return 0;
}

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