Submission #1317037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317037		aryan	Group Photo (JOI21_ho_t3)	C++20	44 / 100	5092 ms	444 KiB

Main

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


int main(){
        
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> hs(n + 1);
    vector<int> a(n);
    for(int i = 0;i < n;i++){
        int x;
        cin >> x;
        a[i] = x;
        hs[x] = i + 1;
    }
   
    const i64 inf = 1e18;
    vector<i64> dp(n + 2,inf);
    dp[n + 1] = 0;
    for(int i = n;i >= 1;i--){
        for(int j = i;j <= n;j++){
            i64 tot = 0;
            vector<int> nhs(n + 1);
            nhs = hs;
            for(int k = i;k <= j;k++){
                int s = hs[k] + 1;
                for(int p = s;p <= n;p++){
                    if(a[p - 1] < i) nhs[k] ++;
                    if(a[p - 1] >= i && a[p - 1] > k && a[p - 1] <= j) nhs[k] ++;
                }
            }
             for(int k = i;k <= j;k++){
                tot += abs(nhs[j - (k - i)] - k);
            }
            dp[i] = min(dp[j + 1] + tot,dp[i]);
        }
    }
    cout << dp[1] << '\n';
    return 0;
}

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