QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#273255#7880. Streak Manipulationucup-team484#WA 1ms3468kbC++171.3kb2023-12-02 22:28:352023-12-02 22:28:37

Judging History

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

  • [2023-12-02 22:28:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3468kb
  • [2023-12-02 22:28:35]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, m, k; cin >> n >> m >> k;
	string s; cin >> s;
	vector<int> pref(n + 1);
	for (int i = 0; i < n; i++) {
		pref[i] = (s[i] == '0');
		if (i > 0)
			pref[i] += pref[i - 1];
	}
	pref[n] = pref[n - 1];

	auto ok = [&](int C) {
		vector<vector<int>> dp(k + 1, vector<int>(n + 1, mod));
		vector<int> nx(n + 1), sm(n + 1);
		for (int i = 0; i < n; i++) {
			nx[i] = min(n, max(i + C, i > 0 ? nx[i - 1] : 0));
			while (nx[i] < n && s[nx[i]] == '1')
				nx[i]++;
			sm[i] = pref[nx[i] - 1];
			if (i > 0)
				sm[i] -= pref[i - 1];
			if (i == 0 || s[i - 1] == '0')
				dp[1][nx[i]] = sm[i];
		}
		for (int i = 1; i < k; i++)
			for (int j = 1; j < n; j++)
				if (nx[j] - j >= C)
					dp[i + 1][nx[j]] = min(dp[i + 1][nx[j]], dp[i][j - 1] + sm[j]);
		for (int i = 0; i <= n; i++)
			if (dp[k][i] <= m)
				return 1;
		return 0;
	};

	int lo = 1, hi = n;
	while (lo <= hi) {
		int mi = (lo + hi) / 2;
		if (ok(mi))
			lo = mi + 1;
		else
			hi = mi - 1;
	}
	if (hi == 0)
		hi = -1;
	cout << hi << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3392kb

input:

8 3 2
10110110

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

12 3 3
100100010011

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3428kb

input:

4 4 4
0000

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3468kb

input:

1000 200 5
0001001000101001110010011001101010110101101100010100111110111111010010001100100111100101011100011101011001110010111100100100011001010011000100011111010110100001101110101001110000001000111010000111110100111101100110011010011111000111101001010011000111010111010100101111100000100001011001010...

output:

90

result:

wrong answer 1st numbers differ - expected: '99', found: '90'