Submission #987179

#	Time	Username	Problem	Language	Result	Execution time	Memory
987179		AdamGS	Ancient Books (IOI17_books)	C++17	42 / 100	81 ms	23916 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e9+7;
const int LIM=1e3+7;
ll F[LIM], mi[LIM], ma[LIM], dp[LIM][LIM], dpma[LIM][LIM], dpmi[LIM][LIM], l, r;
ll fnd(ll x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
  if(fnd(a)==fnd(b)) return;
  ma[fnd(a)]=max(ma[fnd(a)], ma[fnd(b)]);
  mi[fnd(a)]=min(mi[fnd(a)], mi[fnd(b)]);
  F[fnd(b)]=fnd(a);
}
ll minimum_walk(vector<int>p, int s) {
  ll n=p.size();
  rep(i, n) F[i]=ma[i]=mi[i]=i;
  rep(i, n) uni(i, p[i]);
  l=0; r=n-1;
  while(l<s && p[l]==l) ++l;
  while(r>s && p[r]==r) --r;
  rep(i, n) {
    dpma[i][i]=ma[fnd(i)];
    dpmi[i][i]=mi[fnd(i)];
    for(int j=i+1; j<n; ++j) {
      dpma[i][j]=max(dpma[i][j-1], ma[fnd(j)]);
      dpmi[i][j]=min(dpmi[i][j-1], mi[fnd(j)]);
    }
  }
  ll ans=0;
  rep(i, n) ans+=abs(p[i]-i);
  for(ll d=r-l; d>0; --d) {
    for(ll a=l; a+d-1<=r; ++a) {
      ll b=a+d-1;
      if(dpmi[a][b]<a) dp[a][b]=dp[a-1][b];
      else if(dpma[a][b]>b) dp[a][b]=dp[a][b+1];
      else if(a==l) dp[a][b]=dp[a][b+1]+2;
      else if(b==r) dp[a][b]=dp[a-1][b]+2;
      else dp[a][b]=min(dp[a-1][b], dp[a][b+1])+2;
    }
  }
  return ans+dp[s][s];
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 0 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 30