Submission #703890

#	Time	Username	Problem	Language	Result	Execution time	Memory
703890		Username4132	Kamenčići (COCI21_kamencici)	C++14	70 / 70	74 ms	87256 KiB

Main

#include<iostream>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)

const int MAXN=360, INF=1000000000;
int arr[MAXN], n, k, dp[MAXN][MAXN][MAXN];
string str;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k >> str;
    dforn(i, n) for(int j=i+2 + (n&1); j<=n; j+=2) forn(can, k){
        int v1=0, v2=0;
        if(can>=(str[i]=='C')){
            int dif = can-(str[i]=='C');
            v1=min(dp[i+1][j-1][dif] + (str[j-1]=='C'), dp[i+2][j][dif] + (str[i+1]=='C'));
        }
        if(can>=(str[j-1]=='C')){
            int dif = can-(str[j-1]=='C');
            v2=min(dp[i+1][j-1][dif] + (str[i]=='C'), dp[i][j-2][dif] + (str[j-2]=='C'));
        }
        dp[i][j][can]=max(v1, v2);
    }
    int mx=0;
    forn(i, k) mx=max(mx, dp[0][n][i]);
    cout << (mx>=k? "DA\n" : "NE\n");
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40