Submission #638050

#	Time	Username	Problem	Language	Result	Execution time	Memory
638050		tvladm2009	Bigger segments (IZhO19_segments)	C++14	13 / 100	1 ms	340 KiB

segments

#include <bits/stdc++.h>

const int MAX_N = 5e5;

int a[MAX_N + 1], dp[MAX_N + 1], aib[MAX_N + 1];
long long sp[MAX_N + 1];

void update(int p, int val) {
  for (int i = p; i <= MAX_N; i += i & -i) {
    aib[i] = std::max(aib[i], val);
  }
}

void add(int n, int p, int sum) {
  int l = std::lower_bound(sp + 1, sp + n + 1, sp[p] + sum) - sp;
  update(l, p);
}

int query(int p) {
  int answer = 0;
  for (int i = p; i >= 1; i -= i & -i) {
    answer = std::max(answer, aib[i]);
  }
  return answer;
}

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);
  int n;
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    sp[i] = sp[i - 1] + a[i];
  }
  for (int i = 1; i <= n; i++) {
    int j = query(i);
    dp[i] = dp[j] + 1;
    add(n, i, sp[i] - sp[j]);
  }
  std::cout << dp[n];
  return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27