Submission #864082

#TimeUsernameProblemLanguageResultExecution timeMemory
864082Tri2k6Kamenčići (COCI21_kamencici)C++17
0 / 70
133 ms524288 KiB
#include <bits/stdc++.h> using namespace std; template<class integer> inline integer to_int(const string& s, size_t* idx = 0, int base = 10) { size_t n = s.size(), i = idx ? *idx : 0; bool sign = false; integer x = 0; if (s[i] == '-') ++i, sign = true; function<int(char)> char_to_digit = [&](char c) { static const int d[] = {'a'-10,'0'}; return tolower(c)-d[isdigit(c)]; }; while (i < n) x *= base, x += char_to_digit(s[i++]); if (idx) *idx = i; return sign ? -x : x; } template<class integer> inline string to_string(integer x, int base = 10) { bool sign = false; string s; if (x < 0) x = -x, sign = true; function<char(int)> digit_to_char = [](int d) { static const char c[] = {'a'-10,'0'}; return c[d < 10]+d; }; do s += digit_to_char(x%base), x /= base; while (x > 0); if (sign) s += '-'; reverse(s.begin(),s.end()); return s; } template<class integer> inline istream& read(istream& is, integer& x) { string s; is >> s, x = to_int<integer>(s); return is; } template<class integer> inline ostream& write(ostream& os, integer x) { return os << to_string(x); } using lll = signed __int128; using ulll = unsigned __int128; inline istream& operator>>(istream& is, lll &x) { return read(is,x); } inline istream& operator>>(istream& is, ulll &x) { return read(is,x); } inline ostream& operator<<(ostream& os, lll x) { return write(os,x); } inline ostream& operator<<(ostream& os, ulll x) { return write(os,x); } #define input cin #define output cout #define ll long long #define ull unsigned long long #define pii pair<int,int> #define endl '\n' #define all(v) v.begin(),v.end() #define sorta(v) sort(v.begin(),v.end()) #define mem(a,b) memset(a,b,sizeof(a)); #define GetBit(u) (u & -u) #define bit(u,i) ((u >> i) & 1) #define mask(i) (1ll << i) #define vi vector<int> #define int128 __int128 #define fi first #define se second #define heap_max(a) priority_queue<a> #define heap_min(a) priority_queue<a, vector<a>, greater <a>> #define pb push_back #define eb emplace_back #define TASK "TASK" const int cs = 2e5 + 7; const int mod = 1e9 + 7; const int INF = mod; const int maxN = 5e2 + 7; const int block_size = 320; const ll oo = 1e18 + 7; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } else return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } else return false; } template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); } template<class X, class Y> void Add(X &x , const Y &y) { x += y; if (x > mod) x -= mod; } template<class X, class Y> void Sub(X &x, const Y &y) { x -= y; if (x < 0) x += mod; } // int n,k; int a[cs]; int cnt = 0; int Prefix[cs]; void nhap() { input >> n >> k; for (int i = 1;i <= n;i++) { char c; input >> c; if (c == 'C') { a[i] = 1; } cnt += a[i]; Prefix[i] = Prefix[i - 1] + a[i]; } } int SumRange(int u,int v) { return Prefix[v] - Prefix[u - 1]; } ll dp[maxN][maxN][maxN]; void Solve() { mem(dp,-1); for (int l = n;l >= 1;l--) { for (int r = l;r <= n;r++) { for (int dem = 0;dem <= n;dem++) { if (dem >= k) { dp[l][r][dem] = 0; continue; } int h = cnt - dem - SumRange(l,r); if (h >= k) dp[l][r][dem] = 1; else { dp[l][r][dem] = (!dp[l + 1][r][h] || (!dp[l][r - 1][h])); } } } } if (dp[1][n][0]) { output << "DA"; } else { output << "NE"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } // auto TIME1 = chrono::steady_clock::now(); int T = 1; // input >> T; while (T--) { nhap(); Solve(); } // auto TIME2 = chrono::steady_clock::now(); // auto DIFF = TIME2 - TIME1; //cerr << "Time: " << fixed << setprecision(8) << chrono::duration<double>(DIFF).count() << "s."; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...