oj.uz

Submission #573649

# Submission time Handle Problem Language Result Execution time Memory
573649 2022-06-07T04:06:36 Z Soul234 Kamenčići (COCI21_kamencici) C++14
70 / 70
 168 ms 350668 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;

const int MX = 355;
int psum[MX], N, K;
int dp[MX][MX][MX][2];
str s;

int calc(int l, int r, int redtaken, int turn) {
    if(redtaken == K) return 0;
    if(psum[N] - (psum[r] - psum[l-1]) - redtaken == K) return 1;
    int &res = dp[l][r][redtaken][turn];
    if(~res) return res;
    res = turn;
    if(!turn) {
        res |= calc(l+1, r, redtaken + (s[l-1] == 'C'), turn^1);
        res |= calc(l, r-1, redtaken + (s[r-1] == 'C'), turn^1);
    }
    else {
        res &= calc(l+1, r, redtaken, turn^1);
        res &= calc(l, r-1, redtaken, turn^1);
    }
    return res;
}

void solve() {
    memset(dp, -1, sizeof dp);
    cin>>N>>K;
    cin>>s;
    F0R(i,N) psum[i+1] = psum[i] + (s[i] == 'C');
    cout << (calc(1, N, 0, 0) ? "DA" : "NE") << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 350412 KB Output is correct
2 Correct 140 ms 350404 KB Output is correct
3 Correct 137 ms 350484 KB Output is correct
4 Correct 131 ms 350408 KB Output is correct
5 Correct 140 ms 350404 KB Output is correct
6 Correct 158 ms 350384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 350412 KB Output is correct
2 Correct 140 ms 350404 KB Output is correct
3 Correct 137 ms 350484 KB Output is correct
4 Correct 131 ms 350408 KB Output is correct
5 Correct 140 ms 350404 KB Output is correct
6 Correct 158 ms 350384 KB Output is correct
7 Correct 139 ms 350496 KB Output is correct
8 Correct 155 ms 350468 KB Output is correct
9 Correct 151 ms 350440 KB Output is correct
10 Correct 135 ms 350500 KB Output is correct
11 Correct 133 ms 350456 KB Output is correct
12 Correct 142 ms 350468 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 350412 KB Output is correct
2 Correct 140 ms 350404 KB Output is correct
3 Correct 137 ms 350484 KB Output is correct
4 Correct 131 ms 350408 KB Output is correct
5 Correct 140 ms 350404 KB Output is correct
6 Correct 158 ms 350384 KB Output is correct
7 Correct 139 ms 350496 KB Output is correct
8 Correct 155 ms 350468 KB Output is correct
9 Correct 151 ms 350440 KB Output is correct
10 Correct 135 ms 350500 KB Output is correct
11 Correct 133 ms 350456 KB Output is correct
12 Correct 142 ms 350468 KB Output is correct
13 Correct 129 ms 350504 KB Output is correct
14 Correct 168 ms 350668 KB Output is correct
15 Correct 141 ms 350508 KB Output is correct
16 Correct 150 ms 350472 KB Output is correct
17 Correct 137 ms 350412 KB Output is correct
18 Correct 143 ms 350520 KB Output is correct