QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#277666#7880. Streak Manipulationucup-team059WA 0ms3856kbC++201.0kb2023-12-06 21:19:572023-12-06 21:19:58

Judging History

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

  • [2023-12-06 21:19:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3856kb
  • [2023-12-06 21:19:57]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

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


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, k;
    string s;
    cin >> n >> m >> k >> s;
    s = " " + s;
    vi sum(n + 1);
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] == '0');
    auto check = [=](int x) {
        vector f(n + 1, vi(k + 1, inf));
        f[0][0] = 0;
        for (int 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 (int j = 1; j <= k; j++)
                    f[i][j] = min(f[i][j], f[max(0ll, 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: 3504kb

input:

8 3 2
10110110

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

12 3 3
100100010011

output:

2

result:

ok 1 number(s): "2"

Test #3:

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

input:

4 4 4
0000

output:

0

result:

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