oj.uz

답안 #674288

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
674288 2022-12-23T16:32:21 Z Farhan_HY Kamenčići (COCI21_kamencici) C++14
70 / 70
 209 ms 350572 KB 
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define T int t;cin >> t;while(t--)
#define int long long
#define F first
#define S second
using namespace std;
const int mod = 1e9 + 7;
const int N = 355;
int n, k, a[N], dp[N][N][N];

int Rec(int l, int r, int sum, int s) {
    int x = l - 1 + r - n;
    if (x % 2) {
        if (l == r) return s + a[r] < k;
        if (a[l] + s == k && a[r] + s == k) return 0;
        int &ret = dp[l][r][sum];
        if (ret != -1) return ret;
        ret = 0;
        ret |= !Rec(l + 1, r, sum, s + a[l]);
        ret |= !Rec(l, r - 1, sum, s + a[r]);
        return ret;
    }
    else {
        if (l == r) return sum + a[r] < k;
        if (a[r] + sum == k && a[l] + sum == k) return 0;
        int &ret = dp[l][r][sum];
        if (ret != -1) return ret;
        ret = 0;
        ret |= !Rec(l + 1, r, sum + a[l], s);
        ret |= !Rec(l, r - 1, sum + a[r], s);
        return ret;
    }
}

main() {
    cin >> n >> k;
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++)
        a[i + 1] = s[i] == 'C';
    memset(dp, -1, sizeof dp);
    if (Rec(1, n, 0, 0)) cout << "DA";
    else cout << "NE";
}

Compilation message

Main.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:40:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 350384 KB Output is correct
2 Correct 129 ms 350444 KB Output is correct
3 Correct 124 ms 350572 KB Output is correct
4 Correct 123 ms 350444 KB Output is correct
5 Correct 125 ms 350376 KB Output is correct
6 Correct 140 ms 350496 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 350384 KB Output is correct
2 Correct 129 ms 350444 KB Output is correct
3 Correct 124 ms 350572 KB Output is correct
4 Correct 123 ms 350444 KB Output is correct
5 Correct 125 ms 350376 KB Output is correct
6 Correct 140 ms 350496 KB Output is correct
7 Correct 129 ms 350568 KB Output is correct
8 Correct 125 ms 350412 KB Output is correct
9 Correct 132 ms 350432 KB Output is correct
10 Correct 129 ms 350464 KB Output is correct
11 Correct 138 ms 350480 KB Output is correct
12 Correct 124 ms 350484 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 350384 KB Output is correct
2 Correct 129 ms 350444 KB Output is correct
3 Correct 124 ms 350572 KB Output is correct
4 Correct 123 ms 350444 KB Output is correct
5 Correct 125 ms 350376 KB Output is correct
6 Correct 140 ms 350496 KB Output is correct
7 Correct 129 ms 350568 KB Output is correct
8 Correct 125 ms 350412 KB Output is correct
9 Correct 132 ms 350432 KB Output is correct
10 Correct 129 ms 350464 KB Output is correct
11 Correct 138 ms 350480 KB Output is correct
12 Correct 124 ms 350484 KB Output is correct
13 Correct 125 ms 350380 KB Output is correct
14 Correct 198 ms 350472 KB Output is correct
15 Correct 202 ms 350392 KB Output is correct
16 Correct 209 ms 350408 KB Output is correct
17 Correct 148 ms 350452 KB Output is correct
18 Correct 141 ms 350476 KB Output is correct