# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
106918 | nxteru | 수열 (APIO14_sequence) | C++14 | 542 ms | 83704 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000000000000000
struct t{
ll x,y,q;
};
bool check(t a,t b,t c){
return (c.y-b.y)*(a.x-b.x)<=(b.y-a.y)*(b.x-c.x);
}
int n,m,b[205][100005],l,r;
ll dp[2][100005],s[100005];
t dq[100005];
vector<int>ans;
int main(void){
scanf("%d%d",&n,&m);
m++;
for(int i=1;i<=n;i++){
ll a;
scanf("%d",&a);
s[i]=s[i-1]+a;
}
for(int j=0;j<=n;j++)dp[0][j]=INF;
dp[0][0]=0;
for(int i=1;i<=m;i++){
l=0,r=0;
int o=(i-1)%2,p=i%2;
for(int j=0;j<=n;j++)dp[p][j]=INF;
for(int j=1;j<=n;j++){
if(dp[o][j-1]<INF){
t p=t{-2LL*s[j-1],s[j-1]*s[j-1]+dp[o][j-1],j-1};
while(r-2>=l&&check(dq[r-2],dq[r-1],p))r--;
dq[r++]=p;
while(l+1<r&&dq[l].x*s[j]+dq[l].y>=dq[l+1].x*s[j]+dq[l+1].y)l++;
}
if(l<r){
b[i][j]=dq[l].q;
dp[p][j]=dq[l].x*s[j]+dq[l].y+s[j]*s[j];
}
}
}
printf("%lld\n",(s[n]*s[n]-dp[m%2][n])/2LL);
int x=n;
for(int i=m;i>1;i--){
ans.PB(b[i][x]);
x=b[i][x];
}
for(int i=ans.size()-1;i>=0;i--){
printf("%d",ans[i]);
if(i==0)printf("\n");
else printf(" ");
}
}
컴파일 시 표준 에러 (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... |