Submission #1119036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119036		quanquai	Binaria (CCO23_day1problem1)	C++11	10 / 25	18 ms	12388 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define i64 long long
#define i32 int
#define all(v) (v).begin(), (v).end()
#define task "binaria"

const int N = 1024;
const int mod = 1e6 + 3;

int n, k;
int a[N];

namespace sub3 {
   bool check() {
      return n <= 1000;
   }

    i64 dp[N][1 << 11];

   void solve() {
      for (int msk = 0; msk < (1 << k); msk++) {
         if (__builtin_popcount(msk) == a[1]) {
            dp[1][msk] = 1;
         }
      }
      for (int i = 2; i <= n - k + 1; i++) {
         for (int msk = 0; msk < (1 << k); msk++) {
            if (__builtin_popcount(msk) != a[i - 1]) continue;
            int nmsk = msk & (~(1 << (k - 1)));
            nmsk <<= 1;
            if (__builtin_popcount(nmsk) == a[i]) {
               dp[i][nmsk] += dp[i - 1][msk];
               dp[i][nmsk] %= mod;
            }
            nmsk |= 1;
            if (__builtin_popcount(nmsk) == a[i]) {
               dp[i][nmsk] += dp[i - 1][msk];
               dp[i][nmsk] %= mod;
            }
         }
      }
      i64 ans = 0;
      for (int msk = 0; msk < (1 << k); msk++) {
         if (__builtin_popcount(msk) == a[n - k + 1]) {
            ans += dp[n - k + 1][msk];
            ans %= mod;
         }
      }
      cout << ans;
   }
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);

   if (fopen(task".inp", "r")) {
      freopen(task".inp", "r", stdin);
      freopen(task".out", "w", stdout);
   }

   cin >> n >> k;
   for (int i = 1; i <= n - k + 1; i++) {
      cin >> a[i];
   }

   if (sub3::check()) return sub3::solve(), 0;

  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:60:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |       freopen(task".inp", "r", stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:61:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |       freopen(task".out", "w", stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 7