oj.uz

답안 #638565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638565 2022-09-06T11:46:25 Z NotLinux Kamenčići (COCI21_kamencici) C++14
70 / 70
 175 ms 355412 KB 
/**
 * author: NotLinux
 * created: 06.09.2022 ~ 09:33:06
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
    #include "/home/notlinux/debug.h"
#else
    #define debug(x...) void(37)
#endif
int n,k;string str;
vector<vector<vector<int>>>dp;
vector<int>pre,suff;
//state of a game is  1 if I won this state
//state of a game is  0 if I lost this state
int func(int l,int r,int z){
    if(l+r > n)return 0;
    if(dp[l][r][z]!=-1)return dp[l][r][z];//using dp optimization
 
    int toplam=pre[l]+suff[n-r];//number of the red pebbles in the range [0,l] + [r,n]
    //now we check if the game ends this turn
    if((toplam-z)==k){//has the opponent lost
        dp[l][r][z] = 1;
        return dp[l][r][z];//return that I won in this state
    }
    else if(z == k){//have I lost
        dp[l][r][z] = 0;
        return dp[l][r][z];//return that I lost in this state
    }
 
    //now we check what happens if we go from one of two cases : p1 and p2
    int p1,p2;//two possible cases
    if((l+r)%2==0){//is this my turn
        p1=func(l+1,r,z+(str[l]=='C'));//what happens if I take from left
        p2=func(l,r+1,z+(str[n-r-1]=='C'));//what happens if I take from right
    }
    else {//is this his turn
        p1=func(l+1,r,z);//what happens if he takes from left
        p2=func(l,r+1,z);//what happens if he takes from right
    }
 
 
    //if I won in p1 or p2 , than I won in this state , else I lost in this state , same logic for the opponent
    if((l+r)%2==0){//is this my turn
        dp[l][r][z] = p1|p2;//choose the optimal for urself
    }
    else {//is this his turn
        dp[l][r][z] = p1&p2;//he chooses optimal for himself
    }
 
 
    return dp[l][r][z];//return the state of the game
}
void solve(){
    cin>>n>>k>>str;
 
    dp.assign(n+5,vector<vector<int>>(n+5,vector<int>(n+5,-1)));
    pre.resize(n+1);suff.resize(n+1);
 
    for(int i=0;i<n;i++)pre[i+1]=pre[i]+(str[i]=='C');//building the prefix array
    for(int i=n;i>0;i--)suff[i-1]=suff[i]+(str[i-1]=='C');//building the suffix array
 
    cout<<(func(0,0,0)?"DA":"NE")<<endl;//if I won print DA
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    int tt=1;
    //cin >> tt;
    while(tt--)solve();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 1728 KB Output is correct
10 Correct 1 ms 1364 KB Output is correct
11 Correct 1 ms 1364 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 1728 KB Output is correct
10 Correct 1 ms 1364 KB Output is correct
11 Correct 1 ms 1364 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 151 ms 355412 KB Output is correct
14 Correct 175 ms 353500 KB Output is correct
15 Correct 137 ms 304352 KB Output is correct
16 Correct 171 ms 347728 KB Output is correct
17 Correct 152 ms 349516 KB Output is correct
18 Correct 144 ms 347444 KB Output is correct