Submission #355461

#	Time	Username	Problem	Language	Result	Execution time	Memory
355461		amunduzbaev	Ancient Books (IOI17_books)	C++14	42 / 100	266 ms	12780 KiB

books

#include "books.h"
 
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ll long long
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
 
const ll inf = 1e9+7;
const int N = 1e3+5;
const int mod = 1e9+7;
 
int n, dp[N][N], used[N], last, L[N], R[N], in[N];
int endL, endR;

pii ext(int l, int r){
	int new_l = min(L[in[l]], L[in[r]]), new_r = max(R[in[r]], R[in[l]]);
	while(1){
		if(new_l < l) new_l = min(L[in[--l]], new_l), new_r = max(R[in[l]], new_r);
		else if(new_r > r) new_l = min(L[in[++r]], new_l), new_r = max(R[in[r]], new_r);
		else break;
	}return {new_l, new_r};
}

ll fun(int l, int r){
	if(l < endL || r > endR || l < 0 || r > n) return inf;
	//cout<<l<<" "<<r<<"\n";
	pii tt = ext(l, r);
	l = tt.ff, r = tt.ss;
	if(l == endL && r == endR) return 0;
	int &res = dp[l][r];
	if(res != -1) return res;
	res = min(fun(l-1, r), fun(l, r+1)) + 2;
	return res; 
}

ll minimum_walk(vector<int> p, int s) {
	memset(dp, -1, sizeof dp);
	ll res = 0;
	endL = s, endR = s, n = sz(p);
	
	for(int i=0;i<n;i++){
		if(!used[i]){
			int u = i;
			L[last] = u, R[last] = u;
			do{
				used[u] = 1;
				in[u] = last;
				L[last] = min(L[last], u);
				R[last] = max(R[last], u);
				res += abs(p[u] - u);
				u = p[u];
			}while(u != i);
			if(L[last] != R[last]){
				endL = min(L[last], endL);
				endR = max(R[last], endR);
			}
			last++;
		}
	}
	
	return fun(s, s) + res;
}

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