Submission #1192884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192884		lopkus	Bigger segments (IZhO19_segments)	C++20	13 / 100	0 ms	328 KiB

segments

#include <bits/stdc++.h>

#define int64_t int

int64_t inf = 1e18;

void solve() {
  int n;
  std::cin >> n;
  std::vector<int64_t> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<int64_t> pref(n + 1);
  for(int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  std::vector<std::pair<int,int>> dp(n + 1, {- 1, inf});
  dp[1] = {1, a[1]};
  for(int i = 2; i <= n; i++) {
    int mx = - 1;
    for(int j = i - 1; j >= 0; j--) {
      if(pref[i] >= pref[j] + dp[j].second) {
        mx = std::max(mx, dp[j].first + 1);
      }
    }
    if(mx == - 1) {
      dp[i].first = dp[i - 1].first;
      dp[i].second = dp[i - 1].second + a[i];
    }
    else {
      dp[i].first = mx;
        for(int j = i - 1; j >= 0; j--) {
        if(pref[i] >= pref[j] + dp[j].second) {
          if(dp[j].first + 1 == mx) {
            dp[i].second = std::min(dp[i].second, pref[i] - pref[j]);
          }
        }
      }
    }
  }
  std::cout << dp[n].first;
}


signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

Compilation message (stderr)

segments.cpp:5:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    5 | int64_t inf = 1e18;
      |               ^~~~

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