oj.uz

답안 #887956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887956 2023-12-15T15:25:48 Z fanwen Binaria (CCO23_day1problem1) C++17
10 / 25
 40 ms 8032 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);

const int Mod = 1e6 + 3;
const int MAX = 1e6 + 5;

inline void add(int &x, int y) {
    x += y;
    if(x >= Mod) x -= Mod;
    if(x < 0) x += Mod;
}

int n, k, a[MAX];

namespace sub1 {
    bool check() {
        return n <= 10;
    }

    void solve() {
        int ans = 0;
        for (int mask = 0; mask < (1 << n); ++mask) {
            bool oke = true;
            int sum = 0;
            for (int i = 0; i < n; ++i) {
                sum += (mask >> i & 1);
                if(i >= k) sum -= (mask >> (i - k) & 1);
                if(i + 1 >= k) oke &= a[i + 1 - k] == sum;
            }
            ans += oke;
        }
        cout << ans; exit(0);
    }
}

namespace sub2 {
    bool check() {
        return n <= 1000 && k <= 10;
    }

    int dp[1005][1 << 10];

    void solve() {
        for (int mask = 0; mask < (1 << k); ++mask) {
            if(__builtin_popcount(mask) == a[0]) dp[0][mask] = 1;
        }

        for (int i = 0; i < n - k; ++i) {
            for (int mask = 0; mask < (1 << k); ++mask) {
                int m0 = (mask << 1) & ((1 << k) - 1);
                int m1 = (mask << 1 | 1) & ((1 << k) - 1);
                if(__builtin_popcount(m0) == a[i + 1]) add(dp[i + 1][m0], dp[i][mask]);
                if(__builtin_popcount(m1) == a[i + 1]) add(dp[i + 1][m1], dp[i][mask]);
            }
        }

        cout << accumulate(dp[n - k], dp[n - k] + (1 << k), 0LL) % Mod;
    }
}

void you_make_it(void) {
    cin >> n >> k;
    for (int i = 0; i < n - k + 1; ++i) cin >> a[i];
    reverse(a, a + n - k + 1);
    if(sub2::check()) sub2::solve();
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 7 ms 4700 KB Output is correct
23 Correct 7 ms 4520 KB Output is correct
24 Correct 7 ms 4700 KB Output is correct
25 Correct 7 ms 4700 KB Output is correct
26 Correct 6 ms 4512 KB Output is correct
27 Correct 6 ms 4700 KB Output is correct
28 Correct 4 ms 4700 KB Output is correct
29 Correct 4 ms 4700 KB Output is correct
30 Correct 4 ms 4700 KB Output is correct
31 Correct 4 ms 4692 KB Output is correct
32 Correct 7 ms 4700 KB Output is correct
33 Correct 2 ms 4592 KB Output is correct
34 Correct 3 ms 4700 KB Output is correct

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 7 ms 4700 KB Output is correct
23 Correct 7 ms 4520 KB Output is correct
24 Correct 7 ms 4700 KB Output is correct
25 Correct 7 ms 4700 KB Output is correct
26 Correct 6 ms 4512 KB Output is correct
27 Correct 6 ms 4700 KB Output is correct
28 Correct 4 ms 4700 KB Output is correct
29 Correct 4 ms 4700 KB Output is correct
30 Correct 4 ms 4700 KB Output is correct
31 Correct 4 ms 4692 KB Output is correct
32 Correct 7 ms 4700 KB Output is correct
33 Correct 2 ms 4592 KB Output is correct
34 Correct 3 ms 4700 KB Output is correct
35 Incorrect 40 ms 8032 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 7 ms 4700 KB Output is correct
23 Correct 7 ms 4520 KB Output is correct
24 Correct 7 ms 4700 KB Output is correct
25 Correct 7 ms 4700 KB Output is correct
26 Correct 6 ms 4512 KB Output is correct
27 Correct 6 ms 4700 KB Output is correct
28 Correct 4 ms 4700 KB Output is correct
29 Correct 4 ms 4700 KB Output is correct
30 Correct 4 ms 4700 KB Output is correct
31 Correct 4 ms 4692 KB Output is correct
32 Correct 7 ms 4700 KB Output is correct
33 Correct 2 ms 4592 KB Output is correct
34 Correct 3 ms 4700 KB Output is correct
35 Incorrect 40 ms 8032 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 7 ms 4700 KB Output is correct
23 Correct 7 ms 4520 KB Output is correct
24 Correct 7 ms 4700 KB Output is correct
25 Correct 7 ms 4700 KB Output is correct
26 Correct 6 ms 4512 KB Output is correct
27 Correct 6 ms 4700 KB Output is correct
28 Correct 4 ms 4700 KB Output is correct
29 Correct 4 ms 4700 KB Output is correct
30 Correct 4 ms 4700 KB Output is correct
31 Correct 4 ms 4692 KB Output is correct
32 Correct 7 ms 4700 KB Output is correct
33 Correct 2 ms 4592 KB Output is correct
34 Correct 3 ms 4700 KB Output is correct
35 Incorrect 40 ms 8032 KB Output isn't correct
36 Halted 0 ms 0 KB -