Submission #939969

#	Time	Username	Problem	Language	Result	Execution time	Memory
939969		Marco_Escandon	Group Photo (JOI21_ho_t3)	C++11	100 / 100	905 ms	196528 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(9);
#pragma GCC optimize("Ofast")
typedef long long ll;
struct Fenwick_tree {
    ll n;
    vector<ll> T;
    void update(ll a, ll b) {
        for(; a<n; a+=(a&(-a)))
            T[a]+=b;
    }
    ll query(ll a) {
        ll ans=0;
        for(; a>0; a-=(a&(-a)))
            ans+=T[a];
        return ans;
    }
    ll query(ll a, ll b) { return query(b) - query(a-1); }

    Fenwick_tree(ll N){
        n = N * 2;
        T.assign(n, 0);
    }
};
int main()
{
    optimizar_io
    ll n;
    cin>>n;
    ll cad[n+1];
    for(int i=1; i<=n; i++)
        cin>>cad[i];
    ll dp1[n+1][n+1];
    ll dp[n+1];
    for(int i=1; i<=n; i++)
    {
        Fenwick_tree asd(n+5);
        dp[i]=1e9;
        ll cont=0;
        for(int j=0; j<=n; j++)
        {
            dp1[i][j]=0;
        }
        for(int j=1; j<=n; j++)
        {
            if(cad[j]<i) continue;
            //if(cad[j]==4){ cout<<asd.query(i,cad[j])<<" "<<asd.query(cad[j],n)<<" "<<(cad[j]-i)-asd.query(i,cad[j])<<"\n";}
            dp1[i][cad[j]]+=asd.query(i,cad[j]);
            dp1[i][cad[j]]+=asd.query(cad[j],n);
            dp1[i][cad[j]]-=(cad[j]-i)-asd.query(i,cad[j]);
            asd.update(cad[j],1);
        }
        for(int j=1; j<=n; j++)
            dp1[i][j]+=dp1[i][j-1];           
    }
    dp[0]=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=i; j++)
        {
            dp[i]=min(dp[i],dp[j-1]+dp1[j][i]);
        }
    }
    cout<<dp[n];
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:12: warning: unused variable 'cont' [-Wunused-variable]
   40 |         ll cont=0;
      |            ^~~~

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