Submission #1244736

#TimeUsernameProblemLanguageResultExecution timeMemory
1244736nasjesGroup Photo (JOI21_ho_t3)C++20
64 / 100
49 ms328 KiB
#include <iostream> #include <iomanip> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <map> #include <stack> #include <bitset> #include <string> #include <cstring> #include <iterator> #include <random> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef long double ld; const ll dim = 3*1e3+7; //const ll mod = 1e9 + 7; const ll inf = 1e18 + 77; #define endl "\n" #define fi first #define pb push_back #define se second #define vll vector<ll> ll n, m; ll ext[dim], a[dim], dp[dim], b[dim], rev[dim]; int main() { ll k, t, u0, v0; cin>>n; for(int i=1; i<=n; i++){ cin>>b[i]; a[b[i]]=i; } dp[1]=0; for(int i=1; i<=n; i++){ ll sum=0; dp[i]=inf; ll ans=0; ll cur=0; for(int j=1; j<i; j++){ if(a[j]>a[i])cur++; dp[j]+=cur; } for(int j=i; j>=1; j--) { sum+=rev[j]; if(a[j]<a[i])ans++; dp[i]=min(dp[j-1]+sum+ans, dp[i]); // cout<<dp[j-1]<<" "<<add<<endl; } for(int j=i-1;j>=1; j--){ if(a[j]<a[i]){rev[j]++; } } } cout<<dp[n]<<endl; 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...