QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#581330#2513. A Color GameCSQ#WA 60ms12724kbC++141.6kb2024-09-22 12:04:282024-09-22 12:04:30

Judging History

你现在查看的是最新测评结果

  • [2024-09-22 12:04:30]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:12724kb
  • [2024-09-22 12:04:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i<b;++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size();
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
int dp[7][555][555];
int can[555][555];
string col = "RGBCMYK";
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int m;
    string s;
    cin>>s>>m;

    int n = sz(s);
    vector<int>v(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<7;j++){
            if(s[i] == col[j])v[i] = j;
        }
    }
   // for(int x:v)cout<<x<<" ";
    //cout<<'\n';
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<7;k++)dp[k][i][j] = -1e9;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            if(v[j] != v[i])break;
            dp[v[i]][i][j] = j-i+1;
        }
    }

    for(int len=1;len<n;len++){
        for(int i=0;i+len<n;i++){
            for(int c=0;c<7;c++){
                int l = i;
                int r = i+len;
                for(int j=l;j<r;j++){
                    dp[c][l][r] = max(dp[c][l][r],dp[c][l][j]+dp[c][j+1][r]);
                    if(can[l][j])dp[c][l][r] = max(dp[c][l][r],dp[c][j+1][r]);
                    if(can[j+1][r])dp[c][l][r] = max(dp[c][l][r],dp[c][l][j]);
                }
                if(dp[c][l][r] >= m)can[l][r] = 1;
                //if(dp[c][l][r]>=0)cout<<c<<" "<<l<<" "<<r<<" "<<dp[c][l][r]<<'\n';
            }
        }
    }
    if(can[0][n-1])cout<<"Yes"<<'\n';
    else cout<<"No"<<'\n';

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9772kb

input:

BBBRRRRRRGGGB 3

output:

Yes

result:

ok single line: 'Yes'

Test #2:

score: 0
Accepted
time: 0ms
memory: 11808kb

input:

BBBRRRRRRGGGB 4

output:

No

result:

ok single line: 'No'

Test #3:

score: 0
Accepted
time: 1ms
memory: 11860kb

input:

RRRRGGGRRRRRG 3

output:

Yes

result:

ok single line: 'Yes'

Test #4:

score: 0
Accepted
time: 60ms
memory: 11788kb

input:

GMYCGMRMGYMRMKCBKBMKKBMMKBBKMBMRRMGYKKMBKMYRGGBMRMKKKBRCMKYCCKYGYYKKCKRCYGGKGRBCKMYMRCRGBRRYCCKKRRKRCKMMMGCCGYYKMCRGMKCYBMRRKYYRRKGGRBMCKGBBYYGGGBBYBBRCCMGKKGRGRMRRBRCYGGGKBRKCBYCKMMBRCGKCCYYMMCKGRBYRRGBBCGYKBBMKRBBKGCRBYCKMYKMCKMBRMGGYBKBRBMYGGCKYCMYKBRCCGCYRRRKCKCBKCMCYBKRBKMCCYRBKBGGMGMCBGMBMYCCK 1

output:

Yes

result:

ok single line: 'Yes'

Test #5:

score: 0
Accepted
time: 54ms
memory: 12528kb

input:

KKCCCCCKYYYYYYKKKCRRCCBBBGGMMGCKKBBBBBRCCRRCRRYYCCYYBGGGBKKKBKKKCMKKMCCCGGGCCCCBBBCCKMMMKCCYYBBCCCCCCCCCYYCCCCBMMBRRRBBGGMKKBYMMMYYBBBBYYYYKCCCMMCKKMMMKKGGMBBRRBBBBKKBBBMMMMKKMMMKKKMMYYGMYYYMRRBMMMBGRRGGMMCCGRRBBBGCGGGCBBBCCBGGGGCRKKBBBRRYYYBBBYYKKKYYYBBYYBBBBCCCRKYGGGYYKKKKKKKKKRCCCYKKRRRKKMMMKMMC 2

output:

Yes

result:

ok single line: 'Yes'

Test #6:

score: 0
Accepted
time: 47ms
memory: 11496kb

input:

BYCCCYYBMMMMMMMMGYYYBBBYGBBBGGGKKKKKKGGGKKKBBBBKKBBBYYGGGGYGGGMGGGGMCMCCCMMMYYYYYYYYYYYCCCGGGCCRRRCRRBBBBRCCCCCGYCCCCCCYYCCCGGMGGRRRBCCCBMMMMBRCCCCGYYYGRYYYRRMMMMMRRRRMCBBGGGBBGYYYGGGCCGGGGMMBBGGRRRRGBRRRRYYYYBCCCYCCKKKMMMMCCYGGGYCBBBYYYYCCCCYCCCMMMMYYCBBBBBBBCCCCCGGGGCCCGGGGCCBBBBBGGGGMMMBKKKKMMM 3

output:

Yes

result:

ok single line: 'Yes'

Test #7:

score: 0
Accepted
time: 46ms
memory: 12316kb

input:

RMMMRRRRRRMMMMMMMMMMMMMGGGGBBBBMYYYRRRRRRYYMMGGGGMMMYMMRRRKKKKYYYYYYMMMMMMRRRRRKRKKRKKKKRRRKYYYKKKKYKCCCMMKKKKKMMMCKRRRKKKKRRRRRMMMGGGGGGMMMRCCCCYYYYCCCBBBBCCYCCCCCYYYYRRYYYYRRRRRRRRRRRRRBBBKKKKBRRRRBRRRBBBBBGGGGGGBYGGGGGGYKRBBBBBBRRRCCCCCCCCCRRRRRRRRKCCCCKYYYYKKKMMMMKKKBBMMMMBBBBBBBBKKKKKKRRRR 4

output:

Yes

result:

ok single line: 'Yes'

Test #8:

score: 0
Accepted
time: 41ms
memory: 11400kb

input:

BBKKKKKBBBCCCKKKKKKKKKKKKKCCKGGGGGGGCCCCCCMMMMMMMRRRRRRRRRYYKKKKKKYYYRRRRRKKKKKCBBBBBBBBBBRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRBGGGGGGBBBRRRRMMMMMRMMYYYYYYBBBBMMMMMBBYMMMKGGGGGGGKKKKMGGRRRRRRGGGGRRRRRRRYYYKKKBBBBBBKKKCCCCCCKBBBBBBYBBBBBBBBBBBBBBYYBBBBBBBBBBBYYCCCCCYBBBBBBYRRRRRRYMMMMMMGGGGGGGMMMMMYY 5

output:

Yes

result:

ok single line: 'Yes'

Test #9:

score: 0
Accepted
time: 48ms
memory: 12348kb

input:

BBMMCCCCCCCCCMMMMKKKKKKMMMBCCYMMMMMCYYYYYYYCCCCCMMMMMMMYYYYMMMMCCCYYYYYYYYYCCCCMMMMMMMMCCMMMYCCCCCBBBBBBBBBRRRRRRRRBMMMMMMMGGGGGGGGGGGGGGGGGMMMMMMMMMMGGGGBBBBBBBCCCCCCBBGGCCCCCCMMMCCCCCCCCKKKKKKKCMMMBBCMMMMMMMMCCCBBBKKKKGGGGGGKKKKKBBBBCCCCMMMMMMRRRRRRGGGGRRRRRRRGKKKKKKKKKKKKKKKKKKKKKKMMMMMMMMKKGGGG 6

output:

Yes

result:

ok single line: 'Yes'

Test #10:

score: 0
Accepted
time: 44ms
memory: 11340kb

input:

GGGGGGGGGGGGGGGGRRRRRRRRCCCCYMMMMMMMMCCCCCCCCCCMMMMMMMMMMMMMYYMMMMBBBBBBBBMMMMMYMGGGGGGGGGGGGGGGGGGGGGMMMMMMMMMMMMBBBBBGGGGGGGGGGBBBBBBMMMMKKKKKRRRRRRRRRRRKKKKMMMMMMMYYYYYYYYYYKKKKKKKKKYYYYYBBCKKKGGGGGGGGGGGGKKKKKCCCCMMMMMMMMMMCCCCCBMMMMMMMMMMMBBBBBBBYMMMMMMMMMMMMYYYYYYYYYYYYCGGGGGGGGGGCCCCGG 8

output:

Yes

result:

ok single line: 'Yes'

Test #11:

score: 0
Accepted
time: 37ms
memory: 11216kb

input:

MMMMMMMMMMMMMCCCCCCCCCCCGGGGGGGGGGGGGGGGGGGCCCCCCCCCMMMMKKBBBBBBBBBBBBBBBBKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBBBBBBBBBBBBBRRRRRRRRRRRRRRRMMMMMMMMMMMMMMMCCCCCCCCCCCCCCCCCCCCCCMMMRRRRRRRRRBBBKKKKKKKKKKKKKKKCCCCCCCCCCCCCRRRRRRRRRRRRRRRRRRCCCCCCCCKKKKKKKMKKKKKKKKKKYYYYYYYYYYYYYYYYYYKKKKKKKKKMM 16

output:

Yes

result:

ok single line: 'Yes'

Test #12:

score: 0
Accepted
time: 40ms
memory: 12724kb

input:

GGGGMMMMMMMMMMMMMMMMMMMMMMMMMMRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYMMMMMMMMMMGGGGGGGGGGGGGGGGGKKKKKKKKKKKKKKKKKKKKKKKKKYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKGGGGGGGGGGGGGGGGGGGGGG 30

output:

Yes

result:

ok single line: 'Yes'

Test #13:

score: -100
Wrong Answer
time: 0ms
memory: 11736kb

input:

RGB 1

output:

No

result:

wrong answer 1st lines differ - expected: 'Yes', found: 'No'