/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 580.0 KiB
#3 Accepted 2ms 520.0 KiB
#4 Accepted 2ms 408.0 KiB
#5 Accepted 3ms 832.0 KiB
#6 Accepted 8ms 3.312 MiB
#7 Accepted 15ms 8.109 MiB
#8 Accepted 15ms 8.301 MiB
#9 Accepted 46ms 34.262 MiB
#10 Accepted 107ms 96.141 MiB
#11 Accepted 108ms 96.145 MiB
#12 Accepted 106ms 96.012 MiB
#13 Accepted 108ms 96.145 MiB
#14 Accepted 109ms 96.137 MiB
#15 Accepted 110ms 95.941 MiB
#16 Accepted 110ms 96.137 MiB
#17 Accepted 109ms 96.137 MiB
#18 Accepted 2ms 432.0 KiB

Code

#include<bits/stdc++.h>
using namespace std;
const long long M=2e3+1,MOD=1000000000;
typedef long long ll;
int dp[5001][5001];
int find_cost(char a, char b, char c){
    int total=0;
    while(a!='a'){
        total++;
        if(a=='z')a='a';
        else a++;
    }
    while(b!='b'){
        if(b=='z')b='a';
        else b++;
        total++;
    }
    while(c!='c'){
        if(c=='z')c='a';
        else c++;
        total++;
    }
    return total;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)dp[i][j]=k+1;
            for(int j=0;j<=n;j++)dp[j][0]=0;// base case
        for(int i=3;i<=n;i++){
            int cost=find_cost(s[i-3],s[i-2],s[i-1]);// cost for each substring
            int left_index=i-3;
            for(int j=n-2;j>=1;j--){
                dp[i][j]=min(dp[left_index][j],dp[left_index][j-1]+cost);
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
            }
        }
        int res=0;
        for(int i=1;i<=n;i++)if(dp[n][i]<=k)res=i;
            cout<<res<<"\n";

       
    }


   return 0;
 
}

Information

Submit By
Type
Submission
Problem
P1100 Substring ABC
Language
C++20 (G++ 13.2.0)
Submit At
2024-09-17 10:08:51
Judged At
2024-10-03 12:56:21
Judged By
Score
100
Total Time
110ms
Peak Memory
96.145 MiB