Submission #831728

#	Time	Username	Problem	Language	Result	Execution time	Memory
831728		green_gold_dog	Group Photo (JOI21_ho_t3)	C++17	100 / 100	666 ms	118868 KiB

Main

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef int ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9000000000000000000, INF32 = 2000000000, MOD = 1000000007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
bool assign_min(T& a, T b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
T square(T a) {
	return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
	ll operator() (pair<ll, ll> p) {
		return ((__int128)p.first * MOD + p.second) % INF64;
	}
};

struct segment_tree {
	vector<ll> pref;
	segment_tree(vector<ll> a = vector<ll>(0, 0)) {
        pref.push_back(0);
        for (auto i : a) {
            pref.push_back(pref.back() + i);
        }
	}
	ll get(ll l, ll r) {
		return pref[r] - pref[l];
	}
};

void solve() {
	ll n;
	cin >> n;
	vector<ll> pos(n);
	for (ll i = 0; i < n; i++) {
		ll x;
		cin >> x;
		x--;
		pos[x] = i;
	}
	vector<segment_tree> all;
	for (ll i = 0; i <= n; i++) {
		vector<ll> now(n);
		for (ll j = 0; j < n; j++) {
			now[j] = pos[j] > i;
		}
		all.emplace_back(now);
	}
	vector<ll> dp(n, INF32);
	dp[0] = 0;
	for (ll i = 1; i < n; i++) {
		ll now = 0;
		for (ll j = i - 1; j >= 0; j--) {
			now += all[pos[j + 1]].get(0, j + 1);
			//for (ll k = 0; k <= j; k++) {
			//	if (pos[k] > pos[j + 1]) {
			//		now++;
			//	}
			//}
			ll x = all[pos[j + 1]].get(j + 2, i + 1);
			now += x;
			now -= (i - j - 1) - x;
			//for (ll k = j + 2; k <= i; k++) {
			//	if (pos[k] > pos[j + 1]) {
			//		now++;
			//	} else {
			//		now--;
			//	}
			//}
			assign_min(dp[i], now + dp[j]);
		}
		now = 0;
		for (ll k = 0; k <= i; k++) {
			now += k - all[pos[k]].get(0, k);
			//for (ll l = 0; l < k; l++) {
			//	if (pos[k] > pos[l]) {
			//		now++;
			//	}
			//}
		}
		assign_min(dp[i], now);
	}
	cout << dp.back() << '\n';
}

int main() {
	if (IS_FILE) {
		freopen("", "r", stdin);
		freopen("", "w", stdout);
	}
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
	ll t = 1;
	if (IS_TEST_CASES) {
		cin >> t;
	}
	for (ll i = 0; i < t; i++) {
		solve();
	}
}

Compilation message (stderr)

Main.cpp:12:22: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '9000000000000000000' to '-494665728' [-Woverflow]
   12 | constexpr ll INF64 = 9000000000000000000, INF32 = 2000000000, MOD = 1000000007;
      |                      ^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:120:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |   freopen("", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:121:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   freopen("", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~

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