| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 172838 | RafaelSus | 수열 (APIO14_sequence) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
vector<ll>m,b;
vector<int>idx;
int ptr;
bool bad(int f1,int f2,ll _m,ll _b)
{
int f3=f2;
f2--;
f1--;
m.pb(_m);
b.pb(_b);
bool ok=(b[f3]-b[f1])*(m[f1]-m[f2])>=(b[f2]-b[f1])*(m[f1]-m[f3]);
m.pop_back();
b.pop_back();
return ok;
}
void add(ll _m,ll _b,int _idx){
while(m.size()>=2/*&&((b.back()-_b)*(_m-m[m.size()-2])>=(b[b.size()-2]-_b)*(_m-m.back()))*/){
if(bad(m.size()-2,m.size()-1,_m,_b,)){
m.pop_back();
b.pop_back();
idx.pop_back();
}else break;
}
m.pb(_m);
b.pb(_b);
idx.pb(_idx);
}
ll func(int pos,ll x){
return m[pos]*x+b[pos];
}
pair<ll,int>get(ll x){
if(ptr>=m.size())ptr=m.size()-1;
while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x))ptr++;
return {func(ptr,x),idx[ptr]};
}
int path[N][205];
void print(int st,int k){
if(path[st][k]==0){
cout<<st<<' ';
return;
}
print(path[st][k],k-1);
cout<<st<<' ';
}
ll dp[2][N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
ll a[n+1],pref[n+1]={};
for(int i=1;i<=n;i++){
cin>>a[i];
pref[i]=pref[i-1]+a[i];
}
for(int i=1;i<=n;i++){
dp[1][i]=pref[i]*(pref[n]-pref[i]);
path[i][1]=0;
}
for(int i=2;i<=k;i++){
int v=(i-1)%2;
m.clear();
b.clear();
idx.clear();
ptr=0;
add(0,0,0);
for(int j=i-1;j<=n;j++){
if(j<i){
if(j==i-1){
add(-pref[j],dp[v][j],j);
}
continue;
}
pair<ll,int>tmp=get(pref[n]-pref[j]);
dp[v^1][j]=tmp.first+(pref[n]-pref[j])*pref[j];
path[j][i]=tmp.second;
add(-pref[j],dp[v][j],j);
}
}
ll mx=0,st=1;
for(int i=1;i<=n;i++){
if(dp[k%2][i]>mx){
mx=dp[k%2][i];
st=i;
}
}
cout<<mx<<'\n';
print(st,k);
}