Submission #53935

#TimeUsernameProblemLanguageResultExecution timeMemory
53935nimarSplit the sequence (APIO14_sequence)C++11
0 / 100
2078 ms17816 KiB
#include <iostream> #include <vector> #include <unordered_map> #include <map> #include <utility> #include <tuple> typedef std::tuple<int, int, int> tiii; #define t3 std::make_tuple static std::vector<int> A; static std::vector<int> psum; static std::map<tiii, tiii> DP; static tiii dp(int s, int l, int k); static tiii _dp(int s, int l, int k) { int m1, m1_j, m1_k1; for (int j=1; j<l; j++) { int s1 = (psum[s+j] - psum[s]) * (psum[s+l] - psum[s+j]); int m2, m2_k1; for (int k1=0; k1<k; k1++) { int s2 = std::get<0>(dp(s, j, k1)) + std::get<0>(dp(s+j, l-j, k-1-k1)); if (k1 == 0 or s2 > m2) { m2 = s2; m2_k1 = k1; } } s1 += m2; if (j==1 or s1 > m1) { m1 = s1; m1_j = j; m1_k1 = m2_k1; } } return t3(m1, m1_j, m1_k1); } static tiii dp(int s, int l, int k) { if (l <= 1 or k <= 0) return t3(0, 0, 0); if (l == 2) return t3(A[s] * A[s+1], 1, 0); auto key = t3(s, l, k); auto it = DP.find(key); if (it != DP.end()) return it->second; tiii val = _dp(s, l, k); DP[key] = val; return val; } static std::vector<int> answer; static void recover(int s, int l, int k) { if (l <=1 or k <= 0) return; tiii x = dp(s, l, k); int j = std::get<1>(x); int k1 = std::get<2>(x); answer.push_back(s + j); recover(s, j, k1); recover(s+j, l-j, k - 1 - k1); } int main(int argc, char const *argv[]) { int n, k; std::cin >> n >> k; for (int i=0; i<n; i++) { int a; std::cin >> a; A.push_back(a); } psum.push_back(0); for (int i=0; i<n; i++) psum.push_back(A[i] + psum[i]); std::cout << std::get<0>(dp(0, n, k)) << std::endl; recover(0, n, k); for (int a: answer) std::cout << a << " "; std::cout << std::endl; /* for (auto it = DP.begin(); it != DP.end(); it++) std::cout << "DP " << std::get<0>(it->first) << ", " << std::get<1>(it->first) << ", " << std::get<2>(it->first) << " = " << std::get<0>(it->second) << ", "<< std::get<1>(it->second) << ", " << std::get<2>(it->second) << '\n'; std::cin >> n; */ return 0; }

Compilation message (stderr)

sequence.cpp: In function 'tiii dp(int, int, int)':
sequence.cpp:26:25: warning: 'm2' may be used uninitialized in this function [-Wmaybe-uninitialized]
       if (k1 == 0 or s2 > m2) {
                      ~~~^~~~
sequence.cpp:22:9: note: 'm2' was declared here
     int m2, m2_k1;
         ^~
sequence.cpp:33:14: warning: 'm1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (j==1 or s1 > m1) {
         ~~~~~^~~~~~~~~~
sequence.cpp:17:7: note: 'm1' was declared here
   int m1, m1_j, m1_k1;
       ^~
#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...