제출 #431696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431696		rainboy	고대 책들 (IOI17_books)	C++98	70 / 100	304 ms	38828 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));
			}
		}
		i = 0;
		while (i < s && pp[i] == i)
			i++;
		j = n - 1;
		while (j > s && pp[j] == j)
			j--;
		ans += dp[i][j] * 2;
	}
	return ans;
}

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