Submission #749604

#	Time	Username	Problem	Language	Result	Execution time	Memory
749604		M_W	Split the sequence (APIO14_sequence)	C++17	0 / 100	12 ms	2000 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
long long a[100001], ans = 0;
long long qs[100001];

pair<long long, int> find_best(int l, int r){
  int L = l, R = r;
  while(l < r){
    int mid = (l + r) >> 1;
    int left = qs[mid] - qs[L - 1];
    int right = qs[R] - qs[mid];

    if(right <= left) r = mid;
    else l = mid + 1;
  }
  long long left_val = (qs[l - 1] - qs[L - 1]) * (qs[R] - qs[l - 1]);
  long long right_val = (qs[l] - qs[L - 1]) * (qs[R] - qs[l]);

  if(left_val > right_val) return {left_val, l - 1};
  return {right_val, l};
}

int main(int argc, char* argv[]){
  int N, K; scanf("%d %d", &N, &K);
  for(int i = 1; i <= N; i++){
    scanf("%lld", &a[i]);
    qs[i] = qs[i - 1] + a[i];
  }

  set<pair<int, int>> alls; alls.insert({1, N});
  for(int i = 1; i <= K; i++){
    pair<long long, int> best_cut = {0, 0};
    pair<int, int> cut_pair = {0, 0};
    for(auto [l, r] : alls){
      if(l == r) continue;
      pair<long long, int> res = find_best(l, r);

      if(res.first > best_cut.first){
        best_cut = res;
        cut_pair = {l, r};
      }
    } 
    alls.erase(cut_pair);
    alls.insert({cut_pair.first, best_cut.second});
    alls.insert({best_cut.second + 1, cut_pair.second});

    ans += best_cut.first;
  }
  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main(int, char**)':
sequence.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   int N, K; scanf("%d %d", &N, &K);
      |             ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%lld", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29