QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#718192 | #2513. A Color Game | yuto1115# | WA | 4ms | 4012kb | C++20 | 1.2kb | 2024-11-06 19:56:00 | 2024-11-06 19:56:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i = ll(j)-1; i >= ll(k); i--)
#define rrep(i,k) rrep2(i,k,0)
#define all(a) a.begin(), a.end()
#define SZ(a) ll(a.size())
#define eb emplace_back
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX/4;
bool chmin(auto& a, auto& b) {return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto& b) {return a < b ? a = b, 1 : 0; }
int main(){
cin.tie(0)->sync_with_stdio(0);
string s; cin >> s;
ll n = SZ(s);
ll m; cin >> m;
vvl dp(n, vl(n+1));
rep(i,n) dp[i][i] = 1;
rep2(w,1,n+1){
rep(l,n){
ll r = l+w;
if(r > n) break;
rep2(k,l+1,r){
dp[l][r] |= (dp[l][k] & dp[k][r]);
}
ll right = l;
rep2(i, l+1, r){
if(s[i] == s[l]) right = i;
else break;
}
ll left = r-1;
rrep2(i, r-1, l){
if(s[i] == s[r-1]) left = i;
else break;
}
if(right == r-1){
if(r-l >= m) dp[l][r] = 1;
}
else{
if(s[l] == s[r-1] && right-l+1+r-left >= m) dp[l][r] |= dp[right+1][left];
}
}
}
string ans = "No";
if(dp[0][n]) ans = "Yes";
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3516kb
input:
BBBRRRRRRGGGB 3
output:
Yes
result:
ok single line: 'Yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
BBBRRRRRRGGGB 4
output:
No
result:
ok single line: 'No'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
RRRRGGGRRRRRG 3
output:
Yes
result:
ok single line: 'Yes'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3944kb
input:
GMYCGMRMGYMRMKCBKBMKKBMMKBBKMBMRRMGYKKMBKMYRGGBMRMKKKBRCMKYCCKYGYYKKCKRCYGGKGRBCKMYMRCRGBRRYCCKKRRKRCKMMMGCCGYYKMCRGMKCYBMRRKYYRRKGGRBMCKGBBYYGGGBBYBBRCCMGKKGRGRMRRBRCYGGGKBRKCBYCKMMBRCGKCCYYMMCKGRBYRRGBBCGYKBBMKRBBKGCRBYCKMYKMCKMBRMGGYBKBRBMYGGCKYCMYKBRCCGCYRRRKCKCBKCMCYBKRBKMCCYRBKBGGMGMCBGMBMYCCK 1
output:
Yes
result:
ok single line: 'Yes'
Test #5:
score: 0
Accepted
time: 4ms
memory: 4012kb
input:
KKCCCCCKYYYYYYKKKCRRCCBBBGGMMGCKKBBBBBRCCRRCRRYYCCYYBGGGBKKKBKKKCMKKMCCCGGGCCCCBBBCCKMMMKCCYYBBCCCCCCCCCYYCCCCBMMBRRRBBGGMKKBYMMMYYBBBBYYYYKCCCMMCKKMMMKKGGMBBRRBBBBKKBBBMMMMKKMMMKKKMMYYGMYYYMRRBMMMBGRRGGMMCCGRRBBBGCGGGCBBBCCBGGGGCRKKBBBRRYYYBBBYYKKKYYYBBYYBBBBCCCRKYGGGYYKKKKKKKKKRCCCYKKRRRKKMMMKMMC 2
output:
Yes
result:
ok single line: 'Yes'
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 4012kb
input:
BYCCCYYBMMMMMMMMGYYYBBBYGBBBGGGKKKKKKGGGKKKBBBBKKBBBYYGGGGYGGGMGGGGMCMCCCMMMYYYYYYYYYYYCCCGGGCCRRRCRRBBBBRCCCCCGYCCCCCCYYCCCGGMGGRRRBCCCBMMMMBRCCCCGYYYGRYYYRRMMMMMRRRRMCBBGGGBBGYYYGGGCCGGGGMMBBGGRRRRGBRRRRYYYYBCCCYCCKKKMMMMCCYGGGYCBBBYYYYCCCCYCCCMMMMYYCBBBBBBBCCCCCGGGGCCCGGGGCCBBBBBGGGGMMMBKKKKMMM 3
output:
No
result:
wrong answer 1st lines differ - expected: 'Yes', found: 'No'