Submission #914620

#	Time	Username	Problem	Language	Result	Execution time	Memory
914620		goodspeed0208	Group Photo (JOI21_ho_t3)	C++14	100 / 100	673 ms	393368 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define INF 10000000000000000
#define int long long 
using namespace std;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int>v(n+5);
	vector<int>pos(n+5);
	for (int i = 1 ; i <= n ; i++) {
		cin >> v[i];
		pos[v[i]] = i;
	}
	vector<vector<int> >front(n+5, vector<int>(n+5, 0));
	//" front[i][j] -> 1~j有幾個在i前"
	for (int i = 1 ; i<= n ; i++) {
		front[i][0] = 0;
		for (int j = 1 ; j <= n ; j++) {
			if (pos[j] < pos[i]) front[i][j] = front[i][j-1] + 1;
			else front[i][j] = front[i][j-1];
		}
	}
	vector<int>dp(n, INF);
	vector<vector<int> >cost(n+5, vector<int>(n+5));
	//cost(i-1, j) :[... ][j ...] [ i-1 i-2 ... j+1] ...
	//cost(i, j)  : [... ][j ...] [ i   i-1 ... j+1] ...
	//cost(i+1, j): [... ][j ...] [ i+1 i   ... j+1] ...
	//"cost[i+1][j] = cost[i][j] + (j+1~n 在i+1前) - (j+1~i 在i+1後) "// i > j
	                           
	//"cost[i][j] = cost[i-1][j] + (j+1~n 在i前) - (j+1~i-1 在i後) "// i > j
	vector<int>ans(n+5, INF);
	ans[0] = 0;          
	for (int j = 0 ; j <= n ; j++) {
		//cost[i][0] = 0;
		cost[j+1][j] = ans[j] + (front[j+1][n] - front[j+1][j]);
		ans[j+1] = min(ans[j+1], cost[j+1][j]);
		//cout << j << " " << ans[j] << "\n";
		//cout << j+1 << " " << j << " " << cost[j+1][j] << "\n";
		for (int i = j+2 ; i <= n ; i++) {
			// j j-1 ... [i i-1 ... j+1]
			cost[i][j] = cost[i-1][j] + (front[i][n] - front[i][j]) - ((i-j-1) - (front[i][i-1] - front[i][j]) );
			ans[i] = min(ans[i], cost[i][j]);
			//cout << i << " " << j << " " << cost[i][j] << "\n";
		}
	}
	cout << ans[n] << "\n";
}

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