Submission #1188012

#TimeUsernameProblemLanguageResultExecution timeMemory
1188012versesrevSplit the sequence (APIO14_sequence)C++20
Compilation error
0 ms0 KiB
#include <iostream> #include <vector> #include <limits> #include <numeric> #include <algorithm> int main() { int n, k; std::cin >> n >> k; std::vector<int> xs(n); for (int& x : xs) std::cin >> x; std::vector<long long> sum(n); std::partial_sum(xs.begin(), xs.end(), sum.begin()); long long INF = std::numeric_limits<long long>::max(); std::vector<std::vector<long long>> dp(k+1, std::vector<long long>(n, INF)); std::vector<std::vector<int>> back(k+1, std::vector<int>(n, -1)); for (int i = 0; i < n; ++i) { dp[0][i] = sum[i] * sum[i]; back[0][i] = -1; } for (int ik = 1; ik <= k; ++ik) { for (int i = 0; i < n; ++i) { long long target = sum[i] / (k + 1); int p = std::lower_bound(sum.begin(), sum.begin() + i, sum[i] - target); for (int j = std::max(p+1, ik); j <= i; ++j) { long long r = sum[i] - sum[j-1]; if (r * k > sum[i]) continue; long long v2 = sum[j-1]*sum[j-1]/(k-1) + r*r; if (v2 >= dp[ik][i]) break; long long v = dp[ik-1][j-1] + r*r; if (dp[ik][i] > v) { dp[ik][i] = v; back[ik][i] = j - 1; } } for (int j = std::max(p+1, ik); j >= ik; --j) { long long r = sum[i] - sum[j-1]; if (r * k < sum[i]) continue; long long v2 = sum[j-1]*sum[j-1]/(k-1) + r*r; if (v2 >= dp[ik][i]) break; long long v = dp[ik-1][j-1] + r*r; if (dp[ik][i] > v) { dp[ik][i] = v; back[ik][i] = j - 1; } } } } std::vector<int> ans; for (int p = n - 1, ik = k; ik; --ik) { p = back[ik][p]; ans.push_back(p + 1); } std::ranges::reverse(ans); std::cout << ((sum[n-1] * sum[n-1] - dp[k][n-1]) / 2) << "\n"; for (int v : ans) std::cout << v << " "; std::cout << "\n"; }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:26:31: error: cannot convert '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >' to 'int' in initialization
   26 |       int p = std::lower_bound(sum.begin(),
      |               ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
      |                               |
      |                               __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >
   27 |           sum.begin() + i,
      |           ~~~~~~~~~~~~~~~~     
   28 |           sum[i] - target);
      |           ~~~~~~~~~~~~~~~~