# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
241053 | Nicholas_Patrick | 수열 (APIO14_sequence) | C++17 | 1630 ms | 81776 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int n, k;
vector <long long> a;
vector <long long> memo1, memo2;
vector <vector <int> > opt;
int i;
void solven(int l=1, int r=n, int ll=1, int rr=n){//[], []
if(l>r)
return;
long long best=-1;
int mid=(l+r)/2;
long long&ret=memo2[mid];
int&optt=opt[i][mid];
optt=-1;
ret=-1ll;
for(int i = ll;i <= min(mid, rr);i ++){
if(ret<(a[mid]-a[i])*(a[i]-a[0])+memo1[i]){
optt=i;
ret=(a[mid]-a[i])*(a[i]-a[0])+memo1[i];
}
}
solven(l, mid-1, ll, optt);
solven(mid+1, r, optt, rr);
}
long long solvenk(){
opt.resize(k+1, vector <int> (n+1));
memo1.assign(n+1, 0);
memo2.assign(n+1, 0);
for(i = 1;i <= k;i ++){
solven();
swap(memo1, memo2);
}
return memo1[n];
}
int main(){
scanf("%d%d", &n, &k);
a.resize(n+1);
a[0]=0ll;
for(i = 1;i <= n;i ++){
scanf("%lld", &a[i]);
a[i]+=a[i-1];
}
printf("%lld\n", solvenk());
int j = n;
vector <int> ans;
for(i = k;i;i --){
ans.push_back(opt[i][j]);
j=opt[i][j];
}
sort(ans.begin(), ans.end());
for(int i = 1;i < k;i ++){
while(ans[i-1]>=ans[i]){
ans[i]++;
}
}
for(int i = 0;i < k;i ++){
printf("%d%c", ans[i], i==k-1?'\n':' ');
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |