結果
問題 | No.2076 Concon Substrings (ConVersion) |
ユーザー |
|
提出日時 | 2022-09-16 22:34:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,319 ms / 5,000 ms |
コード長 | 2,250 bytes |
コンパイル時間 | 5,557 ms |
コンパイル使用メモリ | 169,952 KB |
最終ジャッジ日時 | 2025-02-07 10:07:57 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <iostream>#include <vector>#include <string>#include <map>#include <set>#include <queue>#include <algorithm>#include <cmath>#include <iomanip>#include <random>#include <stdio.h>#include <fstream>#include <functional>#include <cassert>using namespace std;#define rep(i,n) for (int i=0;i<n;i+=1)#define append push_back#define all(x) (x).begin(), (x).end()template<class T>using vec = vector<T>;template<class T>using vvec = vec<vec<T>>;template<class T>using vvvec = vec<vvec<T>>;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template<class T>bool chmin(T &a, T b){if (a>b){a = b;return true;}return false;}template<class T>bool chmax(T &a, T b){if (a<b){a = b;return true;}return false;}template<class T>T sum(vec<T> x){T res=0;for (auto e:x){res += e;}return res;}template<class T>void printv(vec<T> x){for (auto e:x){cout<<e<<" ";}cout<<"\n";}template<class T>ostream& operator<<(ostream& os, const vec<T>& A){os << "[";rep(i,A.size()){os << A[i];if (i!=A.size()-1){os << ", ";}}os << "]" ;return os;}int main() {int N,X,Y;cin>>N>>X>>Y;string S;cin>>S;vec<int> A;int i = 0;while (i < N-2){if (S[i]=='c' && S[i+1]=='o' && S[i+2]=='n'){int a = 1;int j = i+3;while (j < N-2){if (S[j]=='c' && S[j+1]=='o' && S[j+2]=='n') {a++;j += 3;}else{break;}}A.push_back(a);i = j;}else{i++;}}int M = 17000;vec<int> dp(2*M+10,-1);dp[0+M] = 0;for (auto a:A){vec<int> ndp(2*M+10,-1);for (int s=-M;s<=M;s++){if (dp[s+M]==-1){continue;}for (int k=0;k<=a/X;k++){int x = k;int y = (a-k*X)/Y;chmax(ndp[s+x-y+M],dp[s+M]+x+y);}}swap(dp,ndp);}int res = 0;for (int s=-M;s<=0;s++){if (dp[s+M]!=-1){chmax(res,dp[s+M]+s);}}if (dp[M+1]!=-1){chmax(res,dp[M+1]);}cout << res << endl;}