oj.uz

Submission #469344

# Submission time Handle Problem Language Result Execution time Memory
469344 2021-08-31T14:22:08 Z 1bin None (KOI17_cook) C++14
0 / 100
 2 ms 2808 KB 
#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];
		}
	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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2808 KB Output is correct
2 Incorrect 2 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2808 KB Output is correct
2 Incorrect 2 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2808 KB Output is correct
2 Incorrect 2 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2808 KB Output is correct
2 Incorrect 2 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2808 KB Output is correct
2 Incorrect 2 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -