Submission #486785

#	Time	Username	Problem	Language	Result	Execution time	Memory
486785		bigDuck	Group Photo (JOI21_ho_t3)	C++14	64 / 100	5042 ms	488 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 h[5001];
int fw[5001];
int ord[5001];

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

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


int get_cost(int i, int j){

for(int k=1; k<i; k++){
    h[k]=k;
}

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

//ordonat corect;
int mn1=0;
for(int i=1; i<=n; i++){
    fw[i]=0;
}

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

//ordonat descrescator
int mn2=0;
for(int i=1; i<=n; i++){
    fw[i]=0;
}

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

return min(mn1, mn2);
}





int dp[5001], opt[5001];

void dc(int l, int r){

int m=(l+r)>>1ll;

if(l!=r){
    if(m>l){dc(l, m-1);}
}


int mn=1e18;
int optm=0;
int optl=opt[m-1];
for(int j=optl; j<m; j++){
    int ac=get_cost(j+1, m)+dp[j];
    if( ac<mn  ){
        optm=j, mn=ac;
    }
}
dp[m]=mn;

if(l!=r){
    dc(m+1, r);
}

}








int32_t main(){
INIT

cin>>n;
for(int i=1; i<=n; i++){
    cin>>H[i];
}
dc(1, n);
cout<<dp[n];

return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dc(long long int, long long int)':
Main.cpp:108:5: warning: variable 'optm' set but not used [-Wunused-but-set-variable]
  108 | int optm=0;
      |     ^~~~

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