Submission #1148626

#TimeUsernameProblemLanguageResultExecution timeMemory
1148626blackslexSplit the sequence (APIO14_sequence)C++20
50 / 100
2094 ms24644 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll, ll>; int n, k; int main() { scanf("%d %d", &n, &k); vector<int> a(n + 5), pref(n + 5); vector<vector<ll>> dp(k + 5, vector<ll>(n + 5)); vector<vector<int>> par(k + 5, vector<int>(n + 5)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); pref[i] = pref[i - 1] + a[i]; } auto get = [&] (int l, int r) { return pref[r] - pref[l - 1]; }; for (int i = 1; i < n; i++) { dp[1][i] = 1LL * get(1, i) * get(i + 1, n); par[1][i] = i; } for (int i = 2; i <= k; i++) { for (int j = 2; j < n; j++) { for (int l = 1; l < j; l++) { ll nval = dp[i - 1][l] + 1LL * get(l + 1, j) * get(j + 1, n); if (nval >= dp[i][j]) { dp[i][j] = nval; par[i][j] = l; } } } } pii xx = {0, 0}; for (int i = 1; i < n; i++) xx = max(xx, {dp[k][i], i}); vector<pii> u{{k, xx.second}}; while (u.back().first != 1) { auto [x, y] = u.back(); u.emplace_back(x - 1, par[x][y]); } reverse(u.begin(), u.end()); printf("%lld\n", xx.first); for (auto &[x, y]: u) printf("%d ", y); }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:45:36: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} [-Wformat=]
   45 |     for (auto &[x, y]: u) printf("%d ", y);
      |                                   ~^    ~
      |                                    |    |
      |                                    int  std::tuple_element<1, std::pair<long long int, long long int> >::type {aka long long int}
      |                                   %lld
sequence.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...