제출 #973679

#제출 시각아이디문제언어결과실행 시간메모리
973679UltraFalconGroup Photo (JOI21_ho_t3)C++17
0 / 100
1 ms344 KiB
#ifndef DEBUG #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,mmx,fma,popcnt") #endif #include <bits/stdc++.h> // #define int long long using ll = long long; using namespace std; const int INF = 1e9; struct Fenwick { int n; vector<int> b; Fenwick(int sz) { n = sz+1; b.assign(n, 0); } int query(int k) { int res = b[0]; for (int i=k; i>0; i-=i&-i) { res += b[i]; } return res; } void update(int k, int x) { for (int i=k+1; i<n; i+=i&-i) { b[i] += x; } } }; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> h(n); for (auto &x : h) { cin >> x; x--; } vector<int> dp(n, INF); for (int i=0; i<n; i++) { // precompute stuff Fenwick fen(n); vector<int> cost(n, 0); int cnt1 = 0; for (int j=0; j<n; j++) { if (h[j] <= i) { cost[h[j]] += cnt1; // TODO: substract #heights to the left with height h: h[j] < h <= i cost[h[j]] -= (j-cnt1) - fen.query(h[j]); } else { cnt1++; } fen.update(h[j], +1); } int cnt2 = 0; for (int j=n-1; j>=0; j--) { if (h[j] <= i) { cost[h[j]] += cnt2; cnt2++; } } int tot_cost = 0; for (int j=i; j>=0; j--) { tot_cost += cost[j]; if (j > 0) { dp[i] = min(dp[i], dp[j-1] + tot_cost); } else { dp[i] = min(dp[i], tot_cost); } } } cout << dp[n-1] << "\n"; }
#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...