Submission #740633

#	Time	Username	Problem	Language	Result	Execution time	Memory
740633		abczz	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	87 ms	8408 KiB

sculpture

#include <iostream>
#define ll long long

using namespace std;

ll n, a, b, f, z, mn, x, y, A[2000], ps[2000], MX[2000][2000], dp[2000][2000];

void AOne() {
  for (int t=40; t>=0; --t) {
    z = (1LL << t);
    for (int i=0; i<n; ++i) {
      dp[i][0] = 1e18;
      if ((ps[i] & x) == 0 && (ps[i] & z) == 0) dp[i][0] = 1;
      for (int k=0; k<i; ++k) {
        y = ps[i]-ps[k];
        if ((y & x) == 0 && (y & z) == 0) {
          dp[i][0] = min(dp[i][0], dp[k][0]+1);
        }
      }
    }
    if (dp[n-1][0] <= b) x += z;
    else f += z;
  }
  cout << f << '\n';
}

void ANot() {
  for (int t=40; t>=0; --t) {
    z = (1LL << t);
    for (int i=0; i<n; ++i) {
      for (int j=0; j<n; ++j) {
        dp[i][j] = 1e18;
        if (!j && (ps[i] & x) == 0) dp[i][j] = ps[i] & z;
        if (!j) continue;
        for (int k=0; k<i; ++k) {
          y = ps[i]-ps[k];
          if (dp[k][j-1] != 1e18 && (y & x) == 0) {
            dp[i][j] = min(dp[i][j], dp[k][j-1] | (y & z));
          }
        }
      }
    }
    mn = 1e18;
    for (int i=a-1; i<b; ++i) {
      mn = min(mn, dp[n-1][i]);
    }
    if (!mn) x += z;
    else f += z;
  }
  cout << f << '\n';
}

int main() {
  cin >> n >> a >> b;
  for (int i=0; i<n; ++i) {
    cin >> A[i];
    if (!i) ps[i] = A[i];
    else ps[i] = ps[i-1]+A[i];
  }
  if (a == 1) AOne();
  else ANot();
}

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