QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#336199#8281. Pangu and Stonesucup-team635#WA 11ms2272kbRust2.8kb2024-02-24 13:55:162024-02-24 13:55:16

Judging History

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

  • [2024-02-24 13:55:16]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:2272kb
  • [2024-02-24 13:55:16]
  • 提交

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,
        x: usize,
        y: usize,
        a: [i32; n],
    }
    let mut sum = a.clone();
    sum.push(0);
    for i in (0..n).rev() {
        sum[i] += sum[i + 1];
    }
    let inf = 10000i32;
    let mut dp = vec![vec![inf; n + 1]; n + 1];
    for i in 0..n {
        dp[i][i + 1] = 0;
    }
    for l in (0..n).rev() {
        let mut ep = vec![vec![inf; n + 1]; n + 1];
        ep[l][0] = 0;
        for r in (l + 1)..(n + 1) {
            for m in l..r {
                if dp[m][r] == inf {
                    continue;
                }
                let val = dp[m][r];
                for k in 1..=n {
                    ep[r][k] = ep[r][k].min(ep[m][k - 1] + val);
                }
            }
            let mut val = inf;
            for j in x..=y {
                val = val.min(ep[r][j]);
            }
            if l + 1 < r && val < inf {
                dp[l][r] = val + sum[l] - sum[r];
                ep[r][1] = ep[r][1].min(dp[l][r]);
            }
        }
    }
    let mut ans = dp[0][n];
    if ans >= inf {
        ans = 0;
    }
    println!("{}", ans);
}

// ---------- 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 ----------

詳細信息

Test #1:

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

input:

3 2 2
1 2 3

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

3 2 3
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

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

input:

4 3 3
1 2 3 4

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: -100
Wrong Answer
time: 11ms
memory: 2076kb

input:

100 4 7
570 608 194 26 243 470 418 119 1000 936 440 302 797 155 676 283 869 60 959 793 158 397 808 656 379 316 485 854 753 280 543 435 756 822 106 561 402 347 99 739 8 682 834 549 812 32 338 765 699 575 575 785 171 504 335 113 284 612 276 518 835 677 865 900 687 48 859 179 343 318 626 812 523 11 400...

output:

0

result:

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