結果

問題 No.2076 Concon Substrings (ConVersion)
ユーザー tentententen
提出日時 2023-02-09 13:41:17
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 3,165 bytes
コンパイル時間 3,410 ms
コンパイル使用メモリ 95,616 KB
実行使用メモリ 728,272 KB
最終ジャッジ日時 2024-07-06 17:00:56
合計ジャッジ時間 11,427 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 3 MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.*;
import java.util.*;
import java.util.stream.*;
public class Main {
static int[][] dp;
static ArrayList<Integer> values = new ArrayList<>();
static int a;
static int b;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner();
int n = sc.nextInt();
a = sc.nextInt();
b = sc.nextInt();
char[] inputs = sc.next().toCharArray();
int count = 0;
int max = 0;
for (int i = 0; i + 2 < n; i++) {
if (inputs[i] == 'c' && inputs[i + 1] == 'o' && inputs[i + 2] == 'n') {
count++;
i += 2;
} else {
if (count / a > 0 || count / b > 0) {
values.add(count);
max += count / a;
}
count = 0;
}
}
if (count / a > 0 || count / b > 0) {
values.add(count);
max += count / a;
}
dp = new int[values.size()][max + 1];
for (int[] arr : dp) {
Arrays.fill(arr, -1);
}
int ans = 0;
for (int i = max; i >= 0; i--) {
int x = dfw(values.size() - 1, i);
int current = Math.min(i, x) * 2;
if (i > x) {
current++;
}
ans = Math.max(ans, current);
}
System.out.println(ans);
}
static int dfw(int idx, int v) {
if (idx < 0) {
if (v == 0) {
return 0;
} else {
return Integer.MIN_VALUE;
}
}
if (dp[idx][v] < 0) {
dp[idx][v] = Integer.MIN_VALUE;
int x = values.get(idx);
for (int i = 0; i * a <= x && i <= v; i++) {
dp[idx][v] = Math.max(dp[idx][v], dfw(idx - 1, v - i) + (x - i * a) / b);
}
}
return dp[idx][v];
}
}
class Utilities {
static String arrayToLineString(Object[] arr) {
return Arrays.stream(arr).map(x -> x.toString()).collect(Collectors.joining("\n"));
}
static String arrayToLineString(int[] arr) {
return String.join("\n", Arrays.stream(arr).mapToObj(String::valueOf).toArray(String[]::new));
}
}
class Scanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
StringBuilder sb = new StringBuilder();
public Scanner() throws Exception {
}
public int nextInt() throws Exception {
return Integer.parseInt(next());
}
public long nextLong() throws Exception {
return Long.parseLong(next());
}
public double nextDouble() throws Exception {
return Double.parseDouble(next());
}
public int[] nextIntArray() throws Exception {
return Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
public String next() throws Exception {
while (!st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
return st.nextToken();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0