Submission #1274341

#TimeUsernameProblemLanguageResultExecution timeMemory
1274341dorkikannGroup Photo (JOI21_ho_t3)C++20
100 / 100
262 ms134448 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5e3 + 5; const int INF = 1e9; int DP[N]; int H[N]; int Position[N]; int Help[N][N]; int Help2[N][N]; int Help3[N][N]; void Precalc(int n) { for(int i = 1; i <= n; i++) { for(int j = 1; j < i; j++) Help[i][j] = Help[i][j-1] + (Position[j] > Position[i]); } for(int i = n; i >= 1; i--) { for(int j = i+1; j <= n; j++) { Help2[i][j] = Help2[i][j-1] + (Position[i] > Position[j]); } } } int Find(int a, int b) { int sol = 0; sol += Help[b][b-1]; sol -= Help2[b][a]; sol += (a-b) - Help2[b][a]; return sol; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i++) { cin >> H[i]; Position[H[i]] = i; } Precalc(n); for(int i = 1; i <= n; i++) { DP[i] = INF; int cnt = 0; for(int j = i; j >= 1; j--) { cnt += Find(i, j); DP[i] = min(DP[i], DP[j-1] + cnt); } } cout << DP[n] << "\n"; return 0; }
#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...