Submission #609596

#	Time	Username	Problem	Language	Result	Execution time	Memory
609596		Plurm	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	508 ms	4332 KiB

sculpture

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

int y[2048];
int dp[2048];
bool check[2048][2048];
bool dps[128][128];
long long qs[2048];
int main() {
  int n, a, b;
  scanf("%d%d%d", &n, &a, &b);
  for (int i = 1; i <= n; i++) {
    scanf("%d", y + i);
    qs[i] = qs[i - 1] + y[i];
  }
  long long oldmask = 0ll;
  for (long long bit = 60; bit >= 0; bit--) {
    long long mask = oldmask | ((1ll << bit) - 1ll);
    for (int i = 1; i <= n; i++) {
      long long sum = 0ll;
      for (int j = i; j <= n; j++) {
        sum += y[j];
        check[i][j] = (sum | mask) == mask;
      }
    }
    if (a == 1) {
      for (int i = 1; i <= n; i++) {
        if (check[1][i])
          dp[i] = 1;
        else
          dp[i] = 1e9;
        for (int j = 1; j < i; j++) {
          if (check[j + 1][i]) {
            dp[i] = min(dp[j] + 1, dp[i]);
          }
        }
      }
      if (dp[n] > b) {
        oldmask |= 1ll << bit;
      }
    } else {
      dps[0][0] = true;
      for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
          dps[k][i] = false;
          for (int j = 0; j < i; j++) {
            if (check[j + 1][i] && dps[k - 1][j]) {
              dps[k][i] = true;
            }
          }
        }
      }
      bool ok = false;
      for (int k = a; k <= b; k++)
        ok |= dps[k][n];
      if (!ok) {
        oldmask |= 1ll << bit;
      }
    }
  }
  printf("%lld\n", oldmask);
  return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   scanf("%d%d%d", &n, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d", y + i);
      |     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29