Submission #831715

#TimeUsernameProblemLanguageResultExecution timeMemory
831715green_gold_dogGroup Photo (JOI21_ho_t3)C++17
64 / 100
5056 ms321132 KiB
//#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> tree; ll size; segment_tree(vector<ll> a = vector<ll>(0, 0)) { size = 1; while (size < a.size()) { size *= 2; } tree.resize(size * 2, 0); a.resize(size, 0); build(1, 0, size, a); } ll build(ll v, ll l, ll r, vector<ll>& a) { if (r - l == 1) { return tree[v] = a[l]; } ll mid = (l + r) / 2; return tree[v] = build(v * 2, l, mid, a) + build(v * 2 + 1, mid, r, a); } ll get(ll l, ll r) { return get(1, 0, size, l, r); } ll get(ll v, ll l, ll r, ll ql, ll qr) { if (ql <= l && r <= qr) { return tree[v]; } if (qr <= l || r <= ql) { return 0; } ll mid = (l + r) / 2; return get(v * 2, l, mid, ql, qr) + get(v * 2 + 1, mid, r, ql, qr); } }; 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 constructor 'segment_tree::segment_tree(std::vector<int>)':
Main.cpp:55:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   while (size < a.size()) {
      |          ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:141:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   freopen("", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:142:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   freopen("", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...