# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
863528 | 2023-10-20T14:06:43 Z | SyedShajib | 수열 (APIO14_sequence) | C++17 | 2000 ms | 13400 KB |
#include <iostream> #include <vector> #include <algorithm> int main() { int n, k; std::cin >> n >> k; std::vector<int> a(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(k + 1, -1)); std::vector<std::vector<int>> pos(n + 1, std::vector<int>(k + 1, -1)); dp[0][0] = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j <= k; ++j) { if (dp[i][j] != -1) { long long sum = 0; for (int l = i; l < n; ++l) { sum += a[l]; if (j + 1 <= k && dp[l + 1][j + 1] < dp[i][j] + sum * (l - i + 1)) { dp[l + 1][j + 1] = dp[i][j] + sum * (l - i + 1); pos[l + 1][j + 1] = i; } } } } } std::cout << dp[n][k] << std::endl; int cur = n, curk = k; std::vector<int> splits; while (cur > 0) { splits.push_back(pos[cur][curk]); cur = pos[cur][curk]; --curk; } std::reverse(splits.begin(), splits.end()); for (int i = 0; i < splits.size() - 1; ++i) { std::cout << splits[i] << ' '; } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Integer 0 violates the range [1, 6] |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Integer 0 violates the range [1, 49] |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | Integer 0 violates the range [1, 199] |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 344 KB | Integer 0 violates the range [1, 999] |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 203 ms | 1736 KB | Integer 0 violates the range [1, 9999] |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2095 ms | 13400 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |