Submission #998014

#TimeUsernameProblemLanguageResultExecution timeMemory
998014Qwerty1232Cigle (COI21_cigle)C++17
48 / 100
1039 ms164536 KiB
#include <bits/stdc++.h> int32_t main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<int> input(n); for (auto& i : input) { std::cin >> i; } std::vector<int> prf(n + 1); for (int i = 0; i < n; i++) { prf[i + 1] = prf[i] + input[i]; } std::vector<std::vector<int>> dp(n, std::vector<int>(n)); std::vector<std::array<int, 4>> vec; for (int i = 1; i < n; i++) { int dlt = 0; int sum = 0; for (int j = i, j2 = i; j < n; j++) { sum += input[j]; while (j2 > 0 && prf[i] - prf[j2] < sum) { j2--; } if (j2 > 0 && j + 1 < n && prf[i] - prf[j2] == sum) { dlt++; vec.push_back({j2 - 1, i, j + 1, dlt}); } } } std::sort(vec.begin(), vec.end(), [&](auto a, auto b) { return a[1] < b[1]; }); int vec_ptr = 0; for (int j = 0; j < n; j++) { for (int i = 0; i <= j; i++) { if (i > 0) { dp[i][j] = std::max(dp[i][j], dp[i - 1][j]); } // if (i < j) { // dp[i][j] = std::max(dp[i][j], dp[i + 1][j]); // } } while (vec_ptr < vec.size() && vec[vec_ptr][1] == j) { auto [a, b, c, dlt] = vec[vec_ptr++]; for (int t = 0; c + t < n; t++) { dp[b][c + t] = std::max(dp[b][c + t], dp[a][b - 1] + dlt); } } } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans = std::max(ans, dp[i][j]); } } std::cout << ans << "\n"; return 0; }

Compilation message (stderr)

cigle.cpp: In function 'int32_t main()':
cigle.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while (vec_ptr < vec.size() && vec[vec_ptr][1] == j) {
      |                ~~~~~~~~^~~~~~~~~~~~
#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...