Submission #431691

#	Time	Username	Problem	Language	Result	Execution time	Memory
431691		rainboy	Ancient Books (IOI17_books)	C++98	50 / 100	170 ms	18756 KiB

books

#include "books.h"
#include <string.h>

using namespace std;

const int N = 1000000;
const int SMALL = 1000;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

typedef vector<int> vi;

int dd[N];
int dp[SMALL][SMALL];

long long minimum_walk(vi pp, int s) {
	int n = pp.size(), i, j;
	long long ans;

	ans = 0;
	for (i = 0; i < n; i++)
		if (i < pp[i])
			ans += pp[i] - i, dd[i]++, dd[pp[i]]--;
		else if (i > pp[i])
			ans += i - pp[i], dd[pp[i]]++, dd[i]--;
	if (s == 0) {
		for (i = 1; i < n - 1; i++)
			dd[i] += dd[i - 1];
		i = n - 1;
		while (i >= 0 && pp[i] == i)
			i--;
		for (i--; i >= 0; i--)
			if (dd[i] == 0)
				ans += 2;
	} else {
		int l_, r_, l, r;

		for (i = 0; i < n; i++)
			memset(dp[i], 0x3f, n * sizeof *dp[i]);
		dp[s][s] = 0;
		l_ = r_ = pp[s];
		for (i = s; i >= 0; i--) {
			l_ = min(l_, pp[i]), r_ = max(r_, pp[i]);
			l = l_, r = r_;
			for (j = s; j < n; j++) {
				l = min(l, pp[j]), r = max(r, pp[j]);
				if (i > 0)
					dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + (l >= i));
				if (j + 1 < n)
					dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (r <= j));
			}
		}
		ans += dp[0][n - 1] * 2;
	}
	return ans;
}

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