Submission #887956

#	Time	Username	Problem	Language	Result	Execution time	Memory
887956		fanwen	Binaria (CCO23_day1problem1)	C++17	10 / 25	40 ms	8032 KiB

Main

#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 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 7