Submission #469346

#	Time	Username	Problem	Language	Result	Execution time	Memory
469346		1bin	요리 강좌 (KOI17_cook)	C++14	100 / 100	527 ms	124944 KiB

cook

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e3 + 5;
ll n, m, s, e, t, c[NMAX][NMAX], b[NMAX], mn[3], ix[3], x, p[NMAX][NMAX], ans;
deque <pair<ll, ll>> dq[NMAX];

void go(ll idx, ll v) {
	if (v < mn[2]) {
		mn[2] = v; ix[2] = idx;
	}
	for (int k = 2; k; k--)
		if (mn[k - 1] > mn[k]) {
			swap(mn[k - 1], mn[k]);
			swap(ix[k - 1], ix[k]);
		}
	return;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m >> s >> e >> t;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> c[i][j];
			c[i][j] += c[i][j - 1];
		}

	fill(&p[0][0], &p[NMAX - 1][NMAX], 1e18);
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		dq[i].emplace_back(1e18, 0);
		p[i][s] = 0;
	}
	ans = 1e18;
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++) {
			x = p[i][j];
			while (dq[i].size() && dq[i].back().first >= x) dq[i].pop_back();
			dq[i].emplace_back(x, j - s + 1);
			if (dq[i].front().second == j - e) dq[i].pop_front();
		}

		for (int k = 0; k < 3; k++) mn[k] = 1e18;
		for (int i = 1; i <= n; i++) {
			x = dq[i].front().first + c[i][j];
			go(i, x);
		}

		for (int i = 1; i <= n; i++)
			for (int k = 0; k < 3; k++) {
				if (ix[k] == i || ix[k] == b[i]) continue;
				x = mn[k] - c[i][j] + t * (j != m);
				if (j + s <= m) p[i][j + s] = x;
				if (j + e >= m) ans = min(ans, x + c[i][m]);
				break;
			}
	}
	cout << ans;
	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 9 / 9
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 44 / 44