Submission #371233

#	Time	Username	Problem	Language	Result	Execution time	Memory
371233		cheissmart	Group Photo (JOI21_ho_t3)	C++14	100 / 100	971 ms	67840 KiB

Main

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 5005;

int a[N], p[N], dp[N], cost[N][N];

struct BIT {
	int bit[N];
	BIT() {
		memset(bit, 0, sizeof bit);
	}
	void add(int pos, int val) {
		for(; pos < N; pos += pos & -pos)
			bit[pos] += val;
	}
	int qry(int pos) {
		int res = 0;
		for(; pos; pos -= pos & -pos)
			res += bit[pos];
		return res;
	}
} b;

signed main()
{
	IO_OP;

	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		p[a[i]] = i;
	}

	for(int r = 1; r <= n; r++) {
		vi psum(n + 1);
		for(int i = 1; i <= r; i++) psum[p[i]]++;
		for(int i = 1; i <= n; i++) psum[i] += psum[i - 1];
		int ans = 0;
		for(int l = r; l >= 1; l--) {
			ans += psum[n] - psum[p[l]];
			ans -= b.qry(p[l]);
			cost[l][r] = ans;
			b.add(p[l], 1);
		}
		for(int l = r; l >= 1; l--) b.add(p[l], -1);
	}

	dp[0] = 0;
	for(int i = 1; i <= n; i++) {
		dp[i] = INF;
		for(int j = 1; j <= i; j++) {
			dp[i] = min(dp[i], dp[j - 1] + cost[j][i]);
		}
	}
	cout << dp[n] << endl;

}

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