제출 #1226354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226354		Malix	Ancient Books (IOI17_books)	C++20	12 / 100	10 ms	8264 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vi a,vis,arr;
ll dp[1000][1000];

void dfs(int x){
	arr.PB(x);
	vis[x]=1;
	if(vis[a[x]]==0)dfs(a[x]);
}

long long minimum_walk(std::vector<int> p, int s) {
	a=p;
	while(a.size()&&a[a.back()]==a.back())a.pop_back();
	if(a.size()==0)return 0;
	int n=a.size();
	vis.resize(n,0);
	int pos=0;
	while(pos<n&&a[pos]==pos)pos++;
	ll ans=0;
	if(s>=n){
		ans=(s-n+1)*2LL;
		s=n-1;
	}
	vector<pi> L,R,c(n,{-1,-1});
	REP(i,pos,n)if(!vis[i]&&i!=a[i]){
		arr.clear();
		dfs(i);
		sort(all(arr));
		for(auto u:arr)ans+=(ll)abs(u-a[u]);
		L.PB({arr[0],arr.back()});
		R.PB({arr.back(),arr[0]});
		for(auto u:arr)c[u]={arr[0],arr.back()};
	}
	REP(i,0,1000)REP(j,0,1000)dp[i][j]=INF;
	dp[s][s]=0;
	sort(all(L));sort(all(R));
	for(int i=n-1;i>=0;i--)REP(j,i,n)if(dp[i][j]!=INF){
		if(i!=0)dp[i-1][j]=min(dp[i-1][j],dp[i][j]+2);
		if(j!=n-1)dp[i][j+1]=min(dp[i][j+1],dp[i][j]+2);
		auto it=lower_bound(all(L),make_pair(i,0));
		auto it2=lower_bound(all(R),make_pair(i,0));
		if(it!=L.end()){
			auto [x,y]=*it;
			if((x>=i&&x<=j)||(y>=i&&y<=j))dp[min(x,i)][max(j,y)]=min(dp[min(x,i)][max(j,y)],dp[i][j]);
		}
		if(it2!=R.end()){
			auto [y,x]=*it2;
			if((x>=i&&x<=j)||(y>=i&&y<=j))dp[min(x,i)][max(j,y)]=min(dp[min(x,i)][max(j,y)],dp[i][j]);
		}
		if(c[i].F!=-1)dp[min(i,c[i].F)][max(j,c[i].S)]=min(dp[min(i,c[i].F)][max(j,c[i].S)],dp[i][j]);
		if(c[j].F!=-1)dp[min(i,c[j].F)][max(j,c[j].S)]=min(dp[min(i,c[j].F)][max(j,c[j].S)],dp[i][j]);
	}
	return dp[min(pos,s)][n-1]+ans;
}

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