結果
問題 | No.2076 Concon Substrings (ConVersion) |
ユーザー |
![]() |
提出日時 | 2022-09-16 22:41:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,277 bytes |
コンパイル時間 | 2,521 ms |
コンパイル使用メモリ | 224,340 KB |
最終ジャッジ日時 | 2025-02-07 10:12:36 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 12 WA * 16 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic push#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic popusing namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;} int main() {ios::sync_with_stdio(false);cin.tie(0);int n, a, b;cin >> n >> a >> b;string s;cin >> s;VI dpa{0}, dpb, pa, pb;for(int i = 0; i < n;) {if (s.substr(i, 3) != "con") {i++;continue;}int j = i + 3;while(s.substr(j, 3) == "con") j += 3;int cnt = (j - i) / 3;vector<P> ts;rep(i, cnt / a + 1) {int rest = cnt - i * a;int j = rest / b;ts.emplace_back(i, j);}pa = dpa;pb = dpb;int sza = pa.size(), szb = pb.size();rep(i, sza) if (pa[i] != -1) {for(auto [x, y]: ts) {int ni = i + x, nj = y;int mn = min(ni, nj);int v = pa[i] + 2 * mn;ni -= mn, nj -= mn;if (ni) {if (ni >= (int)dpa.size()) dpa.resize(ni + 1, -1);chmax(dpa[ni], v);} else {if (nj >= (int)dpb.size()) dpb.resize(nj + 1, -1);chmax(dpb[nj], v);}}}rep(i, szb) if (pb[i] != -1) {for(auto [x, y]: ts) {int ni = x, nj = i + y;int mn = min(ni, nj);int v = pa[i] + 2 * mn;ni -= mn, nj -= mn;if (ni) {if (ni >= (int)dpa.size()) dpa.resize(ni + 1, -1);chmax(dpa[ni], v);} else {if (nj >= (int)dpb.size()) dpb.resize(nj + 1, -1);chmax(dpb[nj], v);}}}i = j;}int ans = 0;int sza = dpa.size();rep(i, sza) chmax(ans, dpa[i] + (i > 0));for(int x: dpb) chmax(ans, x);cout << ans << '\n';}