Submission #766528

#	Time	Username	Problem	Language	Result	Execution time	Memory
766528		NK_	Group Photo (JOI21_ho_t3)	C++17	100 / 100	316 ms	460 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;

struct BIT {
	int N; V<int> data; 
	void init(int n) { N = n; data = V<int>(N, 0); }
	void add(int p, int x) { for(++p;p<=N;p+=p&-p) data[p-1] += x; } 
	int sum(int l, int r) { return sum(r+1) - sum(l); }
	int sum(int r) { int s = 0; for(;r;r-=r&-r) s += data[r-1]; return s; }
};

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	V<int> A(N); for(auto& x : A) cin >> x;

	V<int> dp(N+1, INF); dp[0] = 0;
	for(int x = 0; x <= N; x++) {

		BIT B; B.init(N+1);
		V<int> amt(N+1);
		int seen = 0;
		for(int i = 0; i < N; i++) if (A[i] > x) {
			int R = N - i - 1;
			int lx = R - (N - x - seen - 1);
			int l = R - (N - A[i] - B.sum(A[i], N));

			// cout << seen << " " << l << " " << lx << endl;

			amt[A[i]] = seen - (l - lx);

			// cout << A[i] << " " << amt[A[i]] << endl;
			B.add(A[i], 1); seen++;
		}


		int cost = dp[x]; 
		// cout << "X: " << x << " " << cost << endl;
		for(int i = x + 1; i <= N; i++) {
			cost += amt[i];	
			// cout << i << " " << cost << endl;
			dp[i] = min(dp[i], cost);
		}
		// cout << endl;
	}

	cout << dp[N] << nl;


    return 0;
}

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