#P5677. 拟剧论

    ID: 6420 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-指定流量最小费用流势能优化费用流DijkstraDAG 动态规划

拟剧论

题目描述

你有 nn 个小时挣脱绳索,每小时选择偷偷切割或晃动。第 ii 个小时切割可获得 cic_i 的进度,晃动可获得 wiw_i 的进度。

每段连续 kk 个小时内,至少有 mcm_c 个小时用于切割,至少有 mwm_w 个小时用于晃动。求最大总进度以及一种能达到它的方案。

输入格式

第一行四个整数 n,k,mc,mwn,k,m_c,m_w。第二行 nn 个整数 cic_i。第三行 nn 个整数 wiw_i。

输出格式

第一行输出最大总进度。第二行输出长度为 nn 的字符串,其中 C 表示切割,W 表示晃动。

如果最大进度正确、方案构造错误,可获得该测试点 50%50\% 的分数。

样例

10 4 1 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
69
WWWCWCWWCC

数据范围

1≤k≤n≤10001\le k\le n\le1000,0≤mw,mc≤k0\le m_w,m_c\le k,mw+mc≤km_w+m_c\le k,0≤wi,ci≤1090\le w_i,c_i\le10^9。

子任务 特殊限制 分值
1 n≤20n\le20 10
2 mw=mc=0m_w=m_c=0
3 所有 wi=0w_i=0 20
4 mw=0m_w=0 或 mc=0m_c=0
5 无 40

本题使用特殊评测。可用原赛的 checker 和 testlib,在本地按输入、选手输出、标准答案的顺序传入文件。

原 PDF 题面