結果

問題 No.2076 Concon Substrings (ConVersion)
ユーザー 👑 AngrySadEightAngrySadEight
提出日時 2022-08-24 13:29:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,540 ms / 5,000 ms
コード長 1,393 bytes
コンパイル時間 759 ms
コンパイル使用メモリ 74,364 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-21 23:14:25
合計ジャッジ時間 12,470 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
int N, A, B;
cin >> N >> A >> B;
string S;
cin >> S;
vector<int> rle(0);
int concnt = 0;
int now_idx = 0;
while(true){
if (now_idx >= N - 2){
if (concnt >= 1){
rle.push_back(concnt);
}
break;
}
else if (S.substr(now_idx, 3) == "con"){
now_idx += 3;
concnt++;
}
else{
now_idx++;
if (concnt >= 1){
rle.push_back(concnt);
}
concnt = 0;
}
}
int INF = 50000;
int len = rle.size();
vector<int> dp1(8338, INF * -1);
vector<int> dp2(8338, INF * -1);
dp1[0] = 0;
for (int i = 0; i < len; i++){
for (int j = 0; j < 8338; j++){
for (int k = 0; k <= (rle[i] / A); k++){
if (j + k >= 8338) continue;
dp2[j + k] = max(dp2[j + k], dp1[j] + (rle[i] - A * k) / B);
}
}
for (int j = 0; j < 8338; j++){
dp1[j] = dp2[j];
dp2[j] = INF * -1;
}
}
int ans = 0;
for (int j = 0; j < 8338; j++){
if (dp1[j] >= j - 1) ans = max(ans, 2 * j - 1);
if (dp1[j] >= j) ans = max(ans, 2 * j);
}
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0