Submission #1285033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285033		third	Group Photo (JOI21_ho_t3)	C++20	100 / 100	489 ms	263388 KiB

Main

#include<bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 5005
#define LOG 17
using namespace std;

// da xem hint
// toi nhan xet duoc: day se co dang: 1 2 3 7 6 5 4 8 10 9... tuc la 1 doan giam, roi nhay len

// hint mau chot: 

bool ghuy4g;

const ll inf = 1e9;

ll n, a[N], idx[N], b[N][N], pf[N][N];
ll cost[N][N];

ll bit[N];

void upd(ll u, ll v) {
	ll idx = u;
	while (idx <= n) {
		bit[idx] += v;
		idx += idx & (-idx);
	}
}

ll get(ll u) {
	ll idx = u, ans = 0;
	while (idx > 0) {
		ans += bit[idx];
		idx -= idx & (-idx);
	}
	return ans;
}

ll dp[N];

void solve() {
	for (int i = 1; i <= n; i ++) {
		dp[i] = inf;
		for (int j = i; j >= 1; j --) {
			dp[i] = min(dp[i], dp[j - 1] + cost[j][i]);
		}
	}
	cout << dp[n];
}

void pre() {
	for (int i = n; i >= 1; i --) {
		for (int j = 1; j <= n; j ++) {
			b[i][j] = b[i + 1][j];
		}
		b[i][idx[i]] ++ ;
		for (int j = 1; j <= n; j ++) {
			pf[i][j] = pf[i][j - 1] + b[i][j];
		}
	}
	
	for (int r = 1; r <= n; r ++) {
		for (int i = 1; i <= n; i ++) {
			bit[i] = 0;
		}
		ll base = 0, sum = 0, base2 = 0;
		for (int l = r; l >= 1; l --) {
			base = base + sum - get(idx[l]);
			base2 = base2 + pf[r + 1][idx[l] - 1]; // -1 hay ko cung duoc
			cost[l][r] = base + base2;
			//cout << l << " " << r << " " << cost[l][r] << endl;
			upd(idx[l], 1);
			sum ++ ;
		}
	}
}

bool klinh;

signed main() {
    //freopen("mario.inp", "r", stdin);
	//freopen("mario.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> n;
   	for (int i = 1; i <= n; i ++) {
   		cin >> a[i];
   		idx[a[i]] = i;
   	}
   	pre();
   	solve();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
   	//cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";//
}

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