Submission #1239557

#TimeUsernameProblemLanguageResultExecution timeMemory
1239557PlayVoltzGroup Photo (JOI21_ho_t3)C++20
100 / 100
302 ms196524 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> #include <random> #include <chrono> #include <fstream> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; vector<int> vect(n+1), dp(n+1, LLONG_MAX/2), id(n+1); vector<vector<int> > psum(n+1, vector<int>(n+1, 0)); for (int i=1; i<=n; ++i)cin>>vect[i], id[vect[i]]=i; for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)psum[i][j]=psum[i][j-1]+(vect[j]>i); dp[0]=0; for (int i=1; i<=n; ++i){ int cost=0; for (int j=i; j>0; --j){ cost+=psum[i][id[j]]+(psum[j][n]-psum[j][id[j]])-(psum[i][n]-psum[i][id[j]]); dp[i]=min(dp[i], dp[j-1]+cost); } } cout<<dp[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...