Submission #35688

#	Time	Username	Problem	Language	Result	Execution time	Memory
35688		funcsr	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	89 ms	6108 KiB

sculpture

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N, A, B;
long long Y[2001];
bool dp[2001][2001];
int dp2[2001];

bool solve(long long X) {
  //cout<<bitset<41>(X)<<"\n";
  if (A == 1) {
    rep(i, N+1) dp2[i] = INF;
    dp2[0] = 0;
    for (int x=0; x<N; x++) {
      if (dp2[x] == INF) continue;
      for (int t=x+1; t<=N; t++) {
        if (((Y[t]-Y[x]) | X) == X) dp2[t] = min(dp2[t], dp2[x]+1);
      }
    }
    return dp2[N] <= B;
  }
  else {
    rep(i, N+1) rep(j, N+1) dp[i][j] = 0;
    dp[0][0] = true;
    bool f = false;
    for (int x=0; x<N; x++) {
      rep(num, x+1) {
        if (!dp[x][num]) continue;
        for (int t=x+1; t<=N; t++) {
          if (((Y[t]-Y[x]) | X) == X) dp[t][num+1] = true;
        }
      }
    }
    for (int i=A; i<=B; i++) f |= dp[N][i];
    return f;
  }
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> A >> B;
  rep(i, N) cin >> Y[i+1], Y[i+1] += Y[i];
  long long X = 0;
  for (int i=40; i>=0; i--) {
    if (!solve(X | ((1LL<<i)-1))) X |= 1LL<<i;
  }
  cout << X << "\n";
  return 0;
}

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