QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#277665#7880. Streak Manipulationucup-team059WA 1ms3556kbC++201.0kb2023-12-06 21:18:372023-12-06 21:18:37

Judging History

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

  • [2023-12-06 21:18:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3556kb
  • [2023-12-06 21:18:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i32 = int32_t;
using vi = vector<i32>;
const i32 inf = 1e9;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    i32 n, m, k;
    string s;
    cin >> n >> m >> k >> s;
    s = " " + s;
    vi sum(n + 1);
    for (i32 i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] == '0');
    auto check = [=](i32 x) {
        vector f(n + 1, vi(k + 1, inf));
        f[0][0] = 0;
        for (i32 i = 1, val; i <= n; i++) {
            f[i] = f[i - 1];
            if (i >= x and s[i - x] != '1') {
                val = sum[i] - sum[i - x];
                for (i32 j = 1; j <= k; j++)
                    f[i][j] = min(f[i][j], f[max(0, i - x - 1)][j - 1] + val);
            }
        }
        return f[n][k] <= m;
    };

    int l = 0, r = n, res = -1;
    for (int mid; l <= r;) {
        mid = (l + r) / 2;
        if (check(mid)) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << res << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3556kb

input:

8 3 2
10110110

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

12 3 3
100100010011

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3476kb

input:

4 4 4
0000

output:

0

result:

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