이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll;
const ll inf=9000000000000000000;
#define fr(i,c,d) for(ll i=c;i<=d;i++)
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pp push
using namespace std;
//int h[200001],p[200001];
//int sum[100001];
//pair<ll,ll>p[100001];
//pair<ll,ll>p1[100001];
//string s;
const ll sz=173;
string str(string x,int l,int r){
string h;
for(int i=l;i<=r;i++){
h+=x[i];
}
return h;
}
ll sum[100001];
ll f[201][100001];
ll p[201][100001];
ll cost(int x,int y){
if(x>y) return 0;
ll z=sum[y]-sum[x-1];
return z*z;
}
void fill(ll k,ll l1,ll l2,ll p1,ll p2){
if(l1>l2){
return;
}
ll lm=l1+l2>>1;
p[k][lm]=-1;
f[k][lm]=-1;
for(ll i=p1;i<=p2;i++){
if(lm<=i){
break;
}
ll new_cost=f[k-1][i]+cost(i+1,lm);
if(f[k][lm]==-1){
f[k][lm]=new_cost;
p[k][lm]=i;
}
if(f[k][lm]>new_cost){
f[k][lm]=new_cost;
p[k][lm]=i;
}
}
//cout <<f[k][lm] << ' ' << k << ' ' << lm << endl;
fill(k,l1,lm-1,p1,p[k][lm]);
fill(k,lm+1,l2,p[k][lm],p2);
}
vector<ll>ans;
int main(){
//int color[200001];
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,k;
cin >> n >> k;
k++;
sum[0]=0;
for(ll i=1;i<=n;i++){
ll a;
cin >> a;
sum[i]=sum[i-1]+a;
}
for(ll i=1;i<=n;i++){
f[1][i]=sum[i]*sum[i];
//cout << f[1][i] << endl;
p[1][i]=0;
}
for(ll i=2;i<=k;i++){
fill(i,i,n,i-1,n);
}
ll trans=n;
ll hariu=(sum[n]*sum[n]-f[k][n])/2;
cout << hariu << "\n";
for(ll i=k;i>=2;i--){
ans.pb(p[i][trans]);
trans=p[i][trans];
}
for(ll i=ans.size()-1;i>=0;i--){
cout << ans[i] << ' ';
}
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'void fill(ll, ll, ll, ll, ll)':
sequence.cpp:37:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | ll lm=l1+l2>>1;
| ~~^~~
# | 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... |