Submission #282484

#	Time	Username	Problem	Language	Result	Execution time	Memory
282484		Noam13	Ancient Books (IOI17_books)	C++14	70 / 100	1004 ms	1048580 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define ii pair<int, int>
#define x first
#define y second
#define vii vector<ii>
#define pb push_back
#define all(x) x.begin(), x.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;
const int INF = 1e9;
typedef long long ll;
ll minimum_walk(vi p, int s) {
	ll ans = 0;
	int n = p.size();
	vb check(n,0);
	int needl = s, needr = s;
	vi v1(n), v2(n);
	loop(i,0,n) if(!check[i]){
		vi vec;
		int mn = i, mx = i;
		for(int cur = i;!check[cur]; cur = p[cur]){
			check[cur] = 1;
			ans+=abs(cur-p[cur]);
			vec.pb(cur);
			chkmin(mn, cur); chkmax(mx, cur);
		}
		if (vec.size()>1) chkmax(needr, mx), chkmin(needl, mn);
		for(auto x:vec) v2[x] = mx, v1[x] = mn;
		//cout<<"HI: "<<i<<endl;
	}
	if (s==0){
		int cur = 0, r=0;
		while(cur<=needr){
			if (cur>r) ans+=2;
			chkmax(r, v2[cur++]);
		}
		return ans;
	}
	vvi maxi(n, vi(n)), mini(n, vi(n)), dp(n, vi(n,INF));
	loop(i,0,n) maxi[i][i] = v2[i], mini[i][i] = v1[i];
	loop(k,1,n){
		loop(i,0,n-k){
			int j = i+k;
			maxi[i][j] = max(maxi[i][j-1], maxi[i+1][j]);
			mini[i][j] = min(mini[i][j-1], mini[i+1][j]);
		}
	}
	dp[s][s] = 0;
	loop(k,0,n){
		loop(i,0,n-k){
			int j = i+k;
			if (i) chkmin(dp[i-1][j], dp[i][j]+1);
			if (j<n) chkmin(dp[i][j+1], dp[i][j]+1);
			chkmin(dp[mini[i][j]][maxi[i][j]], dp[i][j]);
		}
	}
	int best = INF;
	loop(i,0,needl+1) loop(j,needr,n) chkmin(best, dp[i][j]);
	ans+=2*best;
	return ans;
}
/*
clear
g++ books.cpp grader.cpp -o a ; ./a
4 0
0 2 3 1

*/

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