Submission #854116

#TimeUsernameProblemLanguageResultExecution timeMemory
854116LeVanThucGroup Photo (JOI21_ho_t3)C++17
100 / 100
4820 ms144388 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define p(x,y) pair<ll,ll>(x,y) #define BIT(i,x) ((x>>i)&1) #define MASK(x) (1<<x) #define ld long double #define __builtin_popcount __builtin_popcountll #define pll pair<ll,ll> template<class T1,class T2> bool maximize(T1 &x,const T2 &y) { if(x<y) { x=y; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &x,const T2 &y) { if(x>y) { x=y; return 1; } return 0; } void online() { std::ios_base::sync_with_stdio(0); cin.tie(0); #ifdef thuc freopen("input.INP","r",stdin); freopen("output.OUT","w",stdout); #endif } const int N=5e3+10,M=1e9+7; struct Node { ll l,r,vl; }Tree[22*N]; ll cnt; vector<ll> Head; ll n,a[N],pos[N]; ll make(ll x,ll y,ll z) { Tree[++cnt].l=x; Tree[cnt].r=y; Tree[cnt].vl=z; return cnt; } ll build(ll l,ll r) { if(l==r) return make(0,0,0); return make(build(l,(l+r)/2),build((l+r)/2+1,r),0); } ll update(ll i,ll l,ll r,ll pos,ll vl) { if(r<pos||pos<l) return i; if(l==r) return make(0,0,vl); ll x=update(Tree[i].l,l,(l+r)/2,pos,vl); ll y=update(Tree[i].r,(l+r)/2+1,r,pos,vl); return make(x,y,Tree[x].vl+Tree[y].vl); } ll query(ll i,ll l,ll r,ll l1,ll r1) { if(r1<l||r<l1) return 0; if(l1<=l&&r<=r1) return Tree[i].vl; return query(Tree[i].l,l,(l+r)/2,l1,r1)+query(Tree[i].r,(l+r)/2+1,r,l1,r1); } ll query(ll l,ll r,ll l1,ll r1) { if(l>r) return 0; return query(Head[r],1,n,l1,r1)-query(Head[l-1],1,n,l1,r1); } ll c[N][N],f[N]; int main() { online(); cin>>n; Head.push_back(build(1,n)); for(int i=1;i<=n;i++) { cin>>a[i]; pos[a[i]]=i; Head.push_back(update(Head.back(),1,n,a[i],1)); } memset(f,0x3f,sizeof f); f[0]=0; for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { c[i][j]=c[i][j-1]; c[i][j]+=query(1,pos[j]-1,i,n); c[i][j]-=query(pos[j],n,i,j-1); minimize(f[j],f[i-1]+c[i][j]); } } cout<<f[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...