Submission #581844

#TimeUsernameProblemLanguageResultExecution timeMemory
581844Koosha_mvAncient Books (IOI17_books)C++14
42 / 100
104 ms24544 KiB
#include "books.h" #include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define Add(x,y) x=(x+y)%mod #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first const int N=1005; const ll inf=1e15; int n,p[N],vis[N],mx1[N],mx2[N],mn1[N],mn2[N]; ll Max[N],dp[N][N]; ll minimum_walk(vector<int> p, int s) { fill(mx1,mx1+N,-1); fill(mx2,mx2+N,-1); fill(mn1,mn1+N,N); fill(mn2,mn2+N,N); ll mx=0,sum=0,ans=0; n=p.size(); int l=n,r=0; f(i,0,n){ sum+=abs(p[i]-i); if(p[i]!=i) minm(l,i),maxm(r,i); } minm(l,s); maxm(r,s); if(l==r) return 0; vector<int> v; f(i,l,r+1) v.pb(p[i]-l); p=v; n=p.size(); f_(i,s,0){ mx1[i]=max(p[i],mx1[i+1]); mn1[i]=min(p[i],mn1[i+1]); } f(i,s,n){ mx2[i]=p[i]; mn2[i]=p[i]; if(i>0){ maxm(mx2[i],mx2[i-1]); minm(mn2[i],mn2[i-1]); } } f(l,0,s+1){ f_(r,n-1,s){ if(l==0 && r==n-1) continue ; if(min(mn1[l],mn2[r])<l){ dp[l][r]=dp[min(mn1[l],mn2[r])][r]; continue ; } if(r<max(mx1[l],mx2[r])){ dp[l][r]=dp[l][max(mx1[l],mx2[r])]; continue ; } dp[l][r]=inf; if(0<l) minm(dp[l][r],dp[l-1][r]+1); if(r+1<n) minm(dp[l][r],dp[l][r+1]+1); //cout<<l<<" "<<r<<" -> "<<dp[l][r]<<endl; } } //eror(dp[s][s]); return 2ll*dp[s][s]+sum; }

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:35:5: warning: unused variable 'mx' [-Wunused-variable]
   35 |  ll mx=0,sum=0,ans=0;
      |     ^~
books.cpp:35:16: warning: unused variable 'ans' [-Wunused-variable]
   35 |  ll mx=0,sum=0,ans=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...