QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#273232 | #7880. Streak Manipulation | ucup-team635# | WA | 46ms | 15120kb | Rust | 3.4kb | 2023-12-02 22:14:57 | 2023-12-02 22:14:58 |
Judging History
answer
use std::io::Write;
use std::collections::*;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
input! {
n: usize,
m: usize,
k: usize,
s: bytes,
}
let mut right = vec![n + 1; n + 2];
// 0の個数
let mut sum = vec![0; n + 1];
for (i, s) in s.iter().enumerate().rev() {
sum[i] = sum[i + 1];
right[i] = right[i + 1];
if *s == b'0' {
right[i] = i;
sum[i] += 1;
}
}
let can = |d: usize| -> bool {
let inf = n + 2;
let mut dp = vec![[inf; 6]; n + 2];
dp[0][0] = 0;
for i in 0..n {
let src = dp[i];
for (dp, src) in dp[i + 1].iter_mut().zip(src.iter()) {
dp.chmin(*src);
}
if i + d <= n {
let need = sum[i] - sum[i + d];
let pos = right[i + d + 1];
for (dp, src) in dp[pos][1..].iter_mut().zip(src.iter()) {
dp.chmin(*src + need);
}
}
}
dp[n..].iter().any(|dp| dp[k] <= m)
};
if !can(1) {
println!("-1");
return;
}
let mut ok = 1;
let mut ng = n + 1;
while ng - ok > 1 {
let mid = (ok + ng) / 2;
if can(mid) {
ok = mid;
} else {
ng = mid;
}
}
println!("{}", ok);
}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
#[macro_export]
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
#[macro_export]
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------
// ---------- begin chmin, chmax ----------
pub trait ChangeMinMax {
fn chmin(&mut self, x: Self) -> bool;
fn chmax(&mut self, x: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
fn chmin(&mut self, x: Self) -> bool {
*self > x && {
*self = x;
true
}
}
fn chmax(&mut self, x: Self) -> bool {
*self < x && {
*self = x;
true
}
}
}
// ---------- end chmin, chmax ----------
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2008kb
input:
8 3 2 10110110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 1948kb
input:
12 3 3 100100010011
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 1988kb
input:
4 4 4 0000
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 2100kb
input:
1000 200 5 0001001000101001110010011001101010110101101100010100111110111111010010001100100111100101011100011101011001110010111100100100011001010011000100011111010110100001101110101001110000001000111010000111110100111101100110011010011111000111101001010011000111010111010100101111100000100001011001010...
output:
99
result:
ok 1 number(s): "99"
Test #5:
score: 0
Accepted
time: 0ms
memory: 2072kb
input:
1000 200 5 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
40
result:
ok 1 number(s): "40"
Test #6:
score: 0
Accepted
time: 0ms
memory: 2040kb
input:
1000 200 5 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 32ms
memory: 14964kb
input:
200000 5 3 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 44ms
memory: 14940kb
input:
200000 5 2 0001010000000000000000010011000001000000000000000001100000000001000000000000010011000010000000000110000010000010000100000000001001010000011000100000000001001000000000011110000100000011000000100110100110001011000000000000000000000000110001000000100000011100010011010001010010010100000000000...
output:
13
result:
ok 1 number(s): "13"
Test #9:
score: 0
Accepted
time: 42ms
memory: 15048kb
input:
200000 5 5 0001100001100000001011100010111101100100110001000011001011111101110100000000000111101001110100010101010100110100100011001100000010110111110010111011110100100101011001100101001010110100011101011001000101011110110010001011111101011101011010101101010001111110101001001110000000000010101001001...
output:
17
result:
ok 1 number(s): "17"
Test #10:
score: 0
Accepted
time: 46ms
memory: 15120kb
input:
200000 5 5 1011101011100110010111011011101110111111101111110111101111011110110111111101111011110101101110001100111110010101111011111101111111111111110110111111111011111111111111111111111111011100101111001110011100111100001111111111110101111011110010111001101111111111110110010101100111111111111111011...
output:
45
result:
ok 1 number(s): "45"
Test #11:
score: -100
Wrong Answer
time: 21ms
memory: 14972kb
input:
200000 5 4 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
24878
result:
wrong answer 1st numbers differ - expected: '24879', found: '24878'