oj.uz

Submission #83173

# Submission time Handle Problem Language Result Execution time Memory
83173 2018-11-05T20:08:56 Z MrTEK Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 2 ms 708 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 2e3 + 5;
const int M = 205;
const ll INF = 1e18;

ll a[N],ans,n,x,y,pre[N],dp[N][2];

ll get(int l,int r) {
  return pre[r] - pre[l - 1];
}

void f(int l,int r,int optl,int optr) {
  if (l > r || optl > optr)
    return;
  int mid = (l + r) / 2;
  int new_opt = mid;
  for (int i = max(mid,optl) ; i <= optr ; i++) {
    if (dp[mid][0] > (dp[i + 1][1] | get(mid, i))) {
      dp[mid][0] = (dp[i + 1][1] | get(mid,i));
      new_opt = i;
    }
  }
  f(l,mid - 1,optl,new_opt);
  f(mid + 1,r,new_opt,optr);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> x >> y;
  for (int i = 1 ; i <= n ; i++) {
    cin >> a[i];
    pre[i] = pre[i - 1] + a[i];
  }
  for (int i = 1 ; i <= y ; i++) {
    for (int j = 1 ; j <= n ; j++) {
      dp[j][1] = dp[j][0];
      dp[j][0] = INF;
    }
    f(1,n,1,n);
    if (i >= x)
      ans = max(ans,dp[1][0]);
  }
  cout << ans << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 552 KB Output is correct
2 Incorrect 2 ms 552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 552 KB Output is correct
2 Incorrect 2 ms 552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 708 KB Output is correct
2 Incorrect 2 ms 708 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 708 KB Output is correct
2 Incorrect 2 ms 708 KB Output isn't correct
3 Halted 0 ms 0 KB -