제출 #43639

#제출 시각아이디문제언어결과실행 시간메모리
43639sorry_Benq수열 (APIO14_sequence)C++14
0 / 100
1 ms488 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll S[100005]; ll DP[100005][205]; const ll INF = 1e18; int main(){ S[0] = 0; int N, K; cin >> N >> K; for (int i = 1; i <= N; i++){ ll x; cin >> x; S[i] = S[i - 1] + x; } for (int i = 1; i <= N; i++){ DP[i][1] = S[i]*S[i]; } for (int j = 2; j <= K + 1; j++){ for (int i = j; i <= N; i++){ DP[i][j] = INF; for (int r = j - 1; r < i; r++){ DP[i][j] = min(DP[i][j], (S[i] - S[r]) * (S[i] - S[r]) + DP[r][j - 1]); } } } cout << (S[N] * S[N] - DP[N][K + 1])/2 << endl; }
#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...