# | 제출 시각UTC-0 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
381776 | jlallas384 | 수열 (APIO14_sequence) | C++17 | 181 ms | 6380 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[1005][205];
ll pref[1005];
int par[1005][205];
int main(){
int n,k;
cin >> n >> k;
vector<int> a(n);
for(auto &x: a){
cin >> x;
}
for(int i = 0; i < n; i++){
pref[i+1] = pref[i] + a[i];
}
ll sm = accumulate(a.begin(),a.end(),0);
int mx = 0,id = 0;
for(int i = 1; i <= n; i++){
sm -= a[i-1];
for(int j = 1; j <= k; j++){
for(int l = 0; l < i; l++){
ll res = dp[l][j-1] + (pref[i] - pref[l]) * sm;
if(res > dp[i][j]){
dp[i][j] = res;
par[i][j] = l;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |