Submission #108940

#	Time	Username	Problem	Language	Result	Execution time	Memory
108940		mirbek01	Bali Sculptures (APIO15_sculpture)	C++11	71 / 100	1071 ms	16248 KiB

sculpture

# include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 2;

int n, a[N], dp[N][N], l, r;
long long pref[N], ans;

bool ok(long long x, int ind){
      for(int i = ind; i <= 40; i ++){
            if((x >> i) % 2 && (ans >> i) % 2 == 0)
                  return 0;
      }
      return 1;
}

bool check(int ind){
      memset(dp, 0, sizeof(dp));
      dp[0][0] = 1;
      for(int i = 1; i <= r; i ++){
            for(int j = 1; j <= n; j ++){
                  for(int k = 0; k < j; k ++){
                        if(ok(pref[j] - pref[k], ind)){
                              dp[i][j] |= dp[i - 1][k];
                        }
                  }
            }
      }
      int ret = 0;
      for(int i = l; i <= r; i ++){
            ret |= dp[i][n];
      }
      return ret;
}

int main(){
      cin >> n >> l >> r;

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

      for(int i = 40; i >= 0; i --){
            if(!check(i))
                  ans += (1LL << i);
      }

      cout << ans << endl;
}

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