QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#713462#7880. Streak Manipulationwyh123WA 8ms23664kbC++201.4kb2024-11-05 19:30:382024-11-05 19:30:39

Judging History

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

  • [2024-11-05 19:30:39]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:23664kb
  • [2024-11-05 19:30:38]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
//#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
int f[N][6][2], n, m, k, num[N];
string a;

int check (int x) {
    memset(f, 0x3f, sizeof f);

    int num0 = 0;
    for (int r = 1, l = 1; r <= n; r ++) {
        if (a[r] == '0') num0 ++;
        if (r - l + 1 == x) {
            num[r] = num0;
            if (a[l ++] == '0') num0 --;
        }
    }
    
    f[0][0][0] = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= k; j ++) {
            if (a[i] == '0') {
                f[i][j][0] = min(f[i - 1][j][0], f[i - 1][j][1]);
                f[i][j][1] = min(f[i - 1][j][1], f[i - 1][j][0]) + 1;
            } else {
                f[i][j][1] = min(f[i - 1][j][1], f[i - 1][j][0]);
            }
            if (i >= x) f[i][j][1] = min(f[i][j][1], f[i - x][j - 1][0] + num[i]);
        }
    }

    return min(f[n][k][1], f[n][k][0]);
}

void solve () {
    cin >> n >> m >> k;
    cin >> a;
    a = " " + a;
    int l = 1, r = n;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid) <= m) l = mid + 1;
        else r = mid - 1;
    }
    l --;

    if (l < 1) cout << -1 << endl;
    else cout << l << endl;

}

signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;

    //cin >> t;
    while (t --) {
        solve ();
    }
    return 0;
}
/*

*/

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 22252kb

input:

8 3 2
10110110

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 8ms
memory: 23000kb

input:

12 3 3
100100010011

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 5ms
memory: 22344kb

input:

4 4 4
0000

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: -100
Wrong Answer
time: 8ms
memory: 23664kb

input:

1000 200 5
0001001000101001110010011001101010110101101100010100111110111111010010001100100111100101011100011101011001110010111100100100011001010011000100011111010110100001101110101001110000001000111010000111110100111101100110011010011111000111101001010011000111010111010100101111100000100001011001010...

output:

96

result:

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