제출 #1278126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278126		nanaseyuzuki	Group Photo (JOI21_ho_t3)	C++20	100 / 100	397 ms	330296 KiB

Main

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
using namespace std;

const int mn = 5e3 + 5, lg2 = 20, mbit = (1 << 20) + 1, mm = 5e3 + 5, inf = 1e9;

int n, a[mn], dp[mn], pos[mn], small[mn][mn], big[mn][mn], prebig[mn][mn], presmall[mn][mn];

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		pos[a[i]] = i;
	}
	// Nx: Dãy kq là dãy có dạng [x, 1] -> [y, x + 1] -> [z, y + 1] -> ...
	for(int i = 1; i <= n; i++){
		for(int j = n; j >= 1; j--){
			big[i][j] = big[i][j + 1] + (pos[j] < pos[i]);
			prebig[i][j] = prebig[i - 1][j] + big[i][j]; 
		}
		for(int j = i - 1; j >= 1; j --){
			small[i][j] = small[i][j + 1] + (pos[j] < pos[i]);
			presmall[i][j] = presmall[i - 1][j] + small[i][j];
		}
	}
	fill(dp, dp + mn, inf);
	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]
				+ prebig[i][i + 1] - prebig[j - 1][i + 1]
				+ presmall[i][j] - presmall[j - 1][j]);
		}
	}
	cout << dp[n] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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