제출 #1103808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103808		Braabebo10	Group Photo (JOI21_ho_t3)	C++17	0 / 100	1 ms	336 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
int main() {
    baraa
    ll n;
    cin>>n;
    vector<ll>a(n),info[n+1];
    for(ll &i:a)cin>>i,i--;
    for(ll i=0;i<n;i++){
        info[i]=info[n]=vector<ll>(n);
        ll k=0;
        for(ll j=i;j>=0;j--)info[i][j]=k++;
        for(ll j=0;j<n;j++)if(a[j]>i)info[i][k++];
    }
    for(ll i=0;i<n;i++)info[n][a[i]]=i;
    function<ll(ll)>solve=[&](ll i)->ll{
        if(i==n)return 0;
        ll ret=LLONG_MAX;
        for(ll j=i;j<n;j++){
            ll c=solve(j+1);
            auto &idx=info[(!i?n:i-1)];
            for(ll k=j,f=i;k>=i;k--,f++) {
//                cout<<i<<' '<<j<<' '<<k<<' '<<f<<' '<<idx[k]<<nl;
                if (idx[k] > f)c += (idx[k] - f);
            }
            ret=min(ret,c);
        }
        return ret;
    };
    cout<<solve(0);
    return 0;
}

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