QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562269#7532. Inspection (32 MB ML!)ucup-team052#WA 1ms7972kbC++235.1kb2024-09-13 16:16:162024-09-13 16:16:17

Judging History

你现在查看的是最新测评结果

  • [2024-09-13 16:16:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7972kb
  • [2024-09-13 16:16:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

const int N = 105, B = 101;

vector <pii> res;
ll dp[N][N][N], dp2[N][N][N];
ll s[10005], ans;
int n, k1, l1, k2, l2;

void solve(int l, int r, int k1, int k2) {
	// fprintf(stderr, "l = %d, r = %d, k1 = %d, k2 = %d\n", l, r, k1, k2);
	if (r - l + 1 <= B) {
		for (int i = 0; i <= k1; i++) {
			for (int j = 0; j <= k2; j++) dp[0][i][j] = 0;
		}
		for (int i = l, cur = 1; i <= r; i++, cur++) {
			int len = i - l + 1;
			assert(cur == len);
			for (int i1 = 0; i1 <= k1; i1++) {
				for (int i2 = 0; i2 <= k2; i2++) {
					dp[cur][i1][i2] = dp[cur - 1][i1][i2];
					if (i1 && cur >= l1) dp[cur][i1][i2] = max(dp[cur][i1][i2], dp[cur - l1][i1 - 1][i2] + s[i] - s[i - l1]);
					if (i2 && cur >= l2) dp[cur][i1][i2] = max(dp[cur][i1][i2], dp[cur - l2][i1][i2 - 1] + s[i] - s[i - l2]);
				}
			}
		}
		int i = r, cur = r - l + 1, i1 = k1, i2 = k2;
		while (i1 || i2) {
			if (dp[cur][i1][i2] == dp[cur - 1][i1][i2]) --i, --cur;
			else if (i1 && cur >= l1 && dp[cur][i1][i2] == dp[cur - l1][i1 - 1][i2] + s[i] - s[i - l1]) {
				res.emplace_back(i - l1, i);
				i -= l1; cur -= l1; --i1;
			} else {
				// fprintf(stderr, "i = %d, cur = %d, i - l2 = %d, i1 = %d, i2 = %d\n", i, cur, i - l2, i1, i2);
				res.emplace_back(i - l2, i);
				i -= l2; cur -= l2; --i2;
			}
		}
		return;
	}
	for (int _ = 0; _ < B; _++) {
		for (int i = 0; i <= k1; i++) {
			/*
			for (int j = 0; j <= k2; j++) {
				dp[0][i][j] = dp2[0][i][j] = 0;
			}
			*/
			memset(dp[_][i], 0, (k2 + 1) * 8);
			memset(dp2[_][i], 0, (k2 + 1) * 8);
		}
	}
	int mid = (l + r) >> 1;
	int cur = 1, cur1, cur2;
	for (int i = l; i <= mid; i++, cur = (cur + 1) % B) {
		int pre0 = cur - 1, pre1 = cur - l1, pre2 = cur - l2;
		if (pre0 < 0) pre0 += B;
		if (pre1 < 0) pre1 += B;
		if (pre2 < 0) pre2 += B;
		int len = i - l + 1;
		for (int i1 = 0; i1 <= k1; i1++) {
			for (int i2 = 0; i2 <= k2; i2++) {
				dp[cur][i1][i2] = dp[pre0][i1][i2];
				if (i1 && len >= l1) dp[cur][i1][i2] = max(dp[cur][i1][i2], dp[pre1][i1 - 1][i2] + s[i] - s[i - l1]);
				if (i2 && len >= l2) dp[cur][i1][i2] = max(dp[cur][i1][i2], dp[pre2][i1][i2 - 1] + s[i] - s[i - l2]);
			}
		}
	}
	cur = (cur + B - 1) % B;
	cur1 = cur; cur = 1;
	for (int i = r; i >= mid + 1; i--, cur = (cur + 1) % B) {
		int pre0 = cur - 1, pre1 = cur - l1, pre2 = cur - l2;
		if (pre0 < 0) pre0 += B;
		if (pre1 < 0) pre1 += B;
		if (pre2 < 0) pre2 += B;
		int len = r - i + 1;
		// fprintf(stderr, "cur = %d, pre0  = %d, pre1 = %d, pre2 = %d\n", cur, pre0, pre1, pre2);
		for (int i1 = 0; i1 <= k1; i1++) {
			for (int i2 = 0; i2 <= k2; i2++) {
				dp2[cur][i1][i2] = dp2[pre0][i1][i2];
				if (i1 && len >= l1) dp2[cur][i1][i2] = max(dp2[cur][i1][i2], dp2[pre1][i1 - 1][i2] + s[i + l1 - 1] - s[i - 1]);
				if (i2 && len >= l2) dp2[cur][i1][i2] = max(dp2[cur][i1][i2], dp2[pre2][i1][i2 - 1] + s[i + l2 - 1] - s[i - 1]);
			}
		}
	}
	cur = (cur + B - 1) % B;
	cur2 = cur;
	ll maxn = -1;
	int L = -1, R = -1, lk1 = -1, lk2 = -1, flag = -1;
	for (int i1 = 0; i1 <= k1; i1++) {
		for (int i2 = 0; i2 <= k2; i2++) {
			ll tmp = dp[cur1][i1][i2] + dp2[cur2][k1 - i1][k2 - i2];
			if (tmp > maxn) {
				maxn = tmp;
				lk1 = i1; lk2 = i2;
				flag = 0;
			}
		}
	}
	for (int i = 1; i <= max(l1, l2) - 1; i++) {
		if (i > mid - l + 1) continue;
		int pos0 = cur1 - i;
		int pos1 = cur2 - (l1 - i);
		int pos2 = cur2 - (l2 - i);
		if (pos0 < 0) pos0 += B;
		if (pos1 < 0) pos1 += B;
		if (pos2 < 0) pos2 += B;
		int lenr = r - mid;
		for (int i1 = 0; i1 <= k1; i1++) {
			for (int i2 = 0; i2 <= k2; i2++) {
				if (lenr >= l1 - i && i1) {
					ll tmp = dp[pos0][i1 - 1][i2] + dp2[pos1][k1 - i1][k2 - i2] + s[mid + l1 - i] - s[mid - i];
					if (tmp > maxn) {
						maxn = tmp;
						L = mid - i; R = mid + l1 - i;
						lk1 = i1 - 1; lk2 = i2; flag = 1;
					}
				}
				if (lenr >= l2 - i && i2) {
					ll tmp = dp[pos0][i1][i2 - 1] + dp2[pos2][k1 - i1][k2 - i2] + s[mid + l2 - i] - s[mid - i];
					// if (tmp == 23) fprintf(stderr, "i = %d, i1 = %d, i2 = %d, %lld %lld %lld\n", i, i1, i2, dp[pos0][i1][i2 - 1], dp2[pos2][k1 - i1][k2 - i2], s[mid + l2 - i] - s[mid - i]);
					if (tmp > maxn) {
						maxn = tmp;
						L = mid - i; R = mid + l2 - i;
						lk1 = i1; lk2 = i2 - 1; flag = 2;
					}
				}
			}
		}
	}
	// fprintf(stderr, "maxn = %lld\n", maxn);
	assert(flag != -1);
	if (flag == 0) {
		solve(l, mid, lk1, lk2);
		solve(mid + 1, r, k1 - lk1, k2 - lk2);
	} else if (flag == 1) {
		res.emplace_back(L, R);
		solve(l, L, lk1, lk2);
		solve(R + 1, r, k1 - lk1 - 1, k2 - lk2);
	} else {
		res.emplace_back(L, R);
		solve(l, L, lk1, lk2);
		solve(R + 1, r, k1 - lk1, k2 - lk2 - 1);
	}
}

int main() {
	cin >> n >> k1 >> l1 >> k2 >> l2;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		s[i] += s[i - 1];
	}
	solve(1, n, k1, k2);
	for (auto i : res) ans += s[i.second] - s[i.first];
	printf("%lld\n", ans);
	printf("%d\n", (int)res.size());
	sort(res.begin(), res.end());
	for (auto i : res) printf("%d %d\n", i.first, i.second);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7972kb

input:

20 2 3 3 2
2 0 2 0 1 2 1 2 1 2 2 2 1 1 2 2 2 1 2 2

output:

22
5
4 6
6 8
9 12
14 17
18 20

result:

wrong answer End of interval should be greater than its beginning