This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int n;
int h[5001],dp[5001][5001],p[5001],ans[5001];
int main()
{
cin>>n;
for(int i=0;i<n;++i)
{
cin>>h[i];
h[i]--;
p[h[i]]=i;
}
for(int i=0;i<n;++i)
{
ordered_set s;
dp[i][i]=0;
s.insert(p[i]);
for(int j=i+1;j<n;++j)
{
dp[i][j]=dp[i][j-1]+s.order_of_key(p[j]);
s.insert(p[j]);
}
}
for(int i=0;i<n;++i)
{
ordered_set s,e;
int v1=0,v2;
int ans1=n*n;
for(int j=0;j<=i;++j)
s.insert(p[j]);
for(int j=i;j>=0;--j)
{
v1-=e.order_of_key(p[j]);
e.insert(p[j]);
s.erase(p[j]);
v1+=s.size()-s.order_of_key(p[j]);
if(j-1==-1)
v2=0;
else
v2=ans[j-1];
ans1=min(ans1,v1+dp[j][i]+v2);
}
ans[i]=ans1;
}
cout<<ans[n-1]<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |