이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int MAX=100005,MAX2=203,inf=2e9;
#define int long long
//typedef pair < ii , int > iii;
using ll = long long;
using ld = long double;
int n;
int a[MAX];
int f[MAX][MAX2];
using ps=pair < int , int >;
using line =pair < int , int >;
ps ii( int a,int b){
if(b<0) return ps(-a,-b);
else return ps(a,b);
}
bool cmp(ps a, ps b){
return a.X*b.Y<a.Y*b.X;
}
bool ss(ps a,int b){
return a.X<b*a.Y;
}
ps giao (line a,line b){
return ii(b.Y-a.Y,a.X-b.X);
}
vector < line > pr[MAX2];
vector < ps > ad[MAX2];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("sequence.inp","r",stdin);freopen("sequence.out","w",stdout);
int m;
cin>>n>>m;
m++;
///dp[i][k]=dp[j][k-1]+a[j]*(a[i]-a[j]);
for(int i=1;i<=m;i++){
cin>>a[i];a[i]+=a[i-1];
f[i][i]=f[i-1][i-1]+a[i-1]*(a[i]-a[i-1]);
ad[i].pb(ii(0,1));
pr[i].pb(line(a[i],f[i][i]-a[i]*a[i]));
line now;
for(int j=i-1;j>1;j--){
int b=0,e=ad[j-1].size()-1,an;
while(b<=e){
int mi=b+e>>1;
if(ss(ad[j-1][mi],a[i])){
b=mi+1;an=mi;
}
else e=mi-1;
}
now=pr[j-1][an];
f[i][j]=now.X*a[i]+now.Y;
//cout<<an<<' '<<i<<' '<<j<<' '<<now.X<<' '<<now.Y<<' '<<a[i]<<' '<<f[i][j]<<'\n';
now=line(a[i],f[i][j]-a[i]*a[i]);
ps x;
while(pr[j].size()>1){
x=giao(pr[j].back(),now);
if((x.Y==0 && now.Y>pr[j].back().Y) || cmp(x,ad[j].back())){
pr[j].pop_back();ad[j].pop_back();
}
else break;
}
x=giao(pr[j].back(),now);
pr[j].pb(now);
ad[j].pb(x);
}
if(i!=1){
now=line(a[i],-a[i]*a[i]);
ps x;
while(pr[1].size()>1){
x=giao(pr[1].back(),now);
if((x.Y==0 && now.Y>pr[1].back().Y) || cmp(x,ad[1].back())){
pr[1].pop_back();ad[1].pop_back();
}
else break;
}
x=giao(pr[1].back(),now);
pr[1].pb(now);
ad[1].pb(x);
}
}
//return 0;
for(int i=m+1;i<=n;i++){
//cerr<<i;
cin>>a[i];a[i]+=a[i-1];
line now;
for(int j=m;j>1;j--){
int b=0,e=ad[j-1].size()-1,an;
while(b<=e){
int mi=b+e>>1;
if(ss(ad[j-1][mi],a[i])){
b=mi+1;an=mi;
}
else e=mi-1;
}
now=pr[j-1][an];
f[i][j]=now.X*a[i]+now.Y;
now=line(a[i],f[i][j]-a[i]*a[i]);
//cout<<i<<' '<<j<<' '<<now.X<<' '<<now.Y<<' '<<a[i]<<' '<<f[i][j]<<'\n';
ps x;
while(pr[j].size()>1){
x=giao(pr[j].back(),now);
if((x.Y==0 && now.Y>pr[j].back().Y) || cmp(x,ad[j].back())){
pr[j].pop_back();ad[j].pop_back();
}
else break;
}
x=giao(pr[j].back(),now);
pr[j].pb(now);
ad[j].pb(x);
}
now=line(a[i],-a[i]*a[i]);
ps x;
while(pr[1].size()>1){
x=giao(pr[1].back(),now);
if((x.Y==0 && now.Y>pr[1].back().Y) || cmp(x,ad[1].back())){
pr[1].pop_back();ad[1].pop_back();
}
else break;
}
x=giao(pr[1].back(),now);
pr[1].pb(now);
ad[1].pb(x);
}
cout<<f[n][m];
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'int main()':
sequence.cpp:51:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mi=b+e>>1;
| ~^~
sequence.cpp:101:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | int mi=b+e>>1;
| ~^~
sequence.cpp:108:27: warning: 'an' may be used uninitialized in this function [-Wmaybe-uninitialized]
108 | now=pr[j-1][an];
| ^
sequence.cpp:58:27: warning: 'an' may be used uninitialized in this function [-Wmaybe-uninitialized]
58 | now=pr[j-1][an];
| ^
# | 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... |