Submission #692496

#	Time	Username	Problem	Language	Result	Execution time	Memory
692496		prairie2022	Group Photo (JOI21_ho_t3)	C++14	100 / 100	55 ms	460 KiB

Main

#include <bits/stdc++.h>
//#define int long long
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
using namespace std;

// how to include ordered_set?

int main(){
    int n, tmp, mindp;
    cin >> n;
    vector<int> p(n+1), dp(n+1, 0);
    for(int i=1; i<=n; i++){
        cin >> tmp;
        p[tmp] = i;
    }
    for(int i=1; i<=n; i++){
        tmp = 0;
        for(int j=1; j<i; j++) tmp += (p[j]>p[i]);
        dp[i-1] +=tmp;
        mindp = dp[i-1];
        for(int j=i-2; j>-1; j--){
            (p[i]>p[j+1])?(tmp++):(tmp--);
            dp[j] += tmp;
            mindp = min(mindp, dp[j]);
        }
        dp[i] = mindp;
    }
    cout << dp[n] << '\n';
    return 0;
}

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