Submission #108944

#	Time	Username	Problem	Language	Result	Execution time	Memory
108944		mirbek01	Bali Sculptures (APIO15_sculpture)	C++11	50 / 100	238 ms	16128 KiB

sculpture

# include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 2;

int n, a[N], dp[N][N], d[N], used[N], l, r;
long long pref[N], ans;
vector <int> g[N];

bool check(){
      if(l > 1){
            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((pref[j] - pref[k]) | ans == ans){
                                    dp[i][j] |= dp[i - 1][k];
                              }
                        }
                  }
            }
            int ret = 0;
            for(int i = l; i <= r; i ++){
                  ret |= dp[i][n];
            }
            return ret;
      } else {
            memset(d, 0x3f3f3f3f, sizeof(d));
            memset(used, 0, sizeof(used));
            for(int i = 0; i < n; i ++){
                  g[i].clear();
                  for(int j = i + 1; j <= n; j ++){
                        if(((pref[j] - pref[i]) | ans) == ans)
                              g[i].push_back(j);
                  }
            }
            d[0] = 0;
            used[0] = 1;
            queue <int> q;
            q.push(0);
            while(!q.empty()){
                  int v = q.front();
                  q.pop();
                  for(int to : g[v]){
                        if(!used[to]){
                              d[to] = d[v] + 1;
                              used[to] = 1;
                              q.push(to);
                        }
                  }
            }
            return d[n] <= r;
      }
}

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

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

      ans = (1LL << 41) - 1;

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

      cout << ans << endl;
}

Compilation message (stderr)

sculpture.cpp: In function 'bool check()':
sculpture.cpp:18:60: warning: self-comparison always evaluates to true [-Wtautological-compare]
                               if((pref[j] - pref[k]) | ans == ans){
                                                        ~~~~^~~~~~
sculpture.cpp:18:60: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]

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