제출 #238034

#제출 시각아이디문제언어결과실행 시간메모리
238034DS007수열 (APIO14_sequence)C++14
33 / 100
84 ms131076 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define evaluate(pt, x) (pt.first * x + pt.second) const int N = 1e5, K = 205; int a[N], s[N], p[K], n, k, dp[N][K], last[N][K]; vector<pair<int, int>> hull[K]; int find(int i, int j, int x) { for (; p[j] < (int)hull[j].size() - 1; p[j]++) { if (evaluate(hull[j][p[j]], x) > evaluate(hull[j][p[j] + 1], x)) break; } last[i][j + 1] = p[j] + j; return evaluate(hull[j][p[j]], x); } int solveTestCase() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; s[0] = a[0]; for (int i = 1; i < n; i++) s[i] = s[i - 1] + a[i]; hull[0].emplace_back(a[0], -a[0] * a[0]); for (int i = 1; i < n; i++) { for (int j = 1; j <= k && j <= i; j++) { dp[i][j] = find(i, j - 1, s[i]); hull[j - 1].emplace_back(s[i], dp[i][j - 1] - s[i] * s[i]); } hull[min(i, k)].emplace_back(s[i], dp[i][min(i, k)] - s[i] * s[i]); } cout << dp[n - 1][k] << "\n"; for (int i = last[n - 1][k], j = k; j > 0; --j, i = last[i][j]) cout << i + 1 << " "; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int test = 1; // cin >> test; while (test--) solveTestCase(); }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'long long int solveTestCase()':
sequence.cpp:37:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
#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...