Submission #602259

#	Time	Username	Problem	Language	Result	Execution time	Memory
602259		HamletPetrosyan	Group Photo (JOI21_ho_t3)	C++17	100 / 100	454 ms	196512 KiB

Main

/// #if (code == true)

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

#define pll pair<long long, long long>
#define len(a) ((int)((a).size()))
#define all(a) a.begin(), a.end()
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 5e3 + 5;

ll n;
ll a[N], ind[N], r[N];
ll pq[N][N], sum[N], x[N];
ll dp[N];

void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		ind[a[i]] = i;
	}
//	cout << endl;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			pq[i][j] = pq[i - 1][j] + pq[i][j - 1] - pq[i - 1][j - 1] + (ind[j] < ind[i]);
			if(i == j) x[i] = x[i - 1] + pq[i][j] - pq[i - 1][j];
//			cout << pq[i][j] << " ";
		}
//		cout << endl;
	}
//	cout << endl;

	for(int i = 1; i <= n; i++){
		r[i] = r[i - 1] + ind[i];
	}

//	for(int i = 1; i <= n; i++){
//		cout << x[i] << " ";
//	}
//	cout << endl << endl;

	fill(dp, dp + n + 2, INF);
	dp[1] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++){
			dp[j + 1] = min(dp[j + 1], dp[i] + x[j] - x[i - 1] - (pq[j][i - 1] - pq[i - 1][i - 1]) + pq[j][n] - pq[i - 1][n] - (pq[j][j] - pq[i - 1][j]));
//			cout << i << " " << j + 1 << " | " << dp[i] << " + " << x[j] << " - " << x[i - 1] << " - (" << pq[j][i - 1] << " - " << pq[i - 1][i - 1] << ") + " << pq[j][n] << " - " << pq[i - 1][n] << " - (" << pq[j][j - 1] << " - " << pq[i - 1][j - 1] << ") = " << dp[j + 1] << endl;
		}
	}
//	for(int i = 1; i <= n; i++){
//		cout << dp[i] << " ";
//	}
	cout << dp[n + 1] << endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int _ = 1;
	// cout << fixed;
	// cout.precision(15);

	// cin >> _ ;
	while(_--) solve();
	return 0;
}

/// #else
/// #include <bits/stdc++.h> using namespace std; int main() { cout << "Hello World!"; }
/// #endif

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