Submission #108942

#	Time	Username	Problem	Language	Result	Execution time	Memory
108942		mirbek01	Bali Sculptures (APIO15_sculpture)	C++11	71 / 100	1067 ms	16248 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 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){
      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(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;
      } 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(ok(pref[j] - pref[i], ind))
                              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];
      }

      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