oj.uz

Submission #949492

# Submission time Handle Problem Language Result Execution time Memory
949492 2024-03-19T09:43:36 Z PM1 Split the sequence (APIO14_sequence) C++17
0 / 100
 26 ms 83464 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=1e5+5,mxk=205;
int n,k,aa[mxn];
int par[mxn][mxk];
ll dp[mxn][2],pre[mxn],ans;
deque<int>cht;
bool comp(int x,int y,ll w,bool z){
	ll xx=(-pre[x])*w+dp[x][z],yy=(-pre[y])*w+dp[y][z];
	return xx>=yy;
}
bool cmp(int x,int y,int w,bool z){
	return (dp[w][z]-dp[y][z])*(pre[y]-pre[x])>=(dp[y][z]-dp[x][z])*(pre[w]-pre[y]);
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>aa[i];
		pre[i]=pre[i-1]+aa[i];
	}
	for(int i=1;i<=n;i++){
		dp[i][1]=pre[i]*(pre[n]-pre[i]);
	}
	for(int j=2;j<=k;j++){
		bool y=j&1;
		cht.push_back(j-1);
		for(int i=j;i<n;i++){
			//ax+b
			ll x=pre[n]-pre[i];
			while(cht.size()>1 && !comp(cht[0],cht[1],x,y^1))cht.pop_front();
			ll a=-pre[cht[0]],b=dp[cht[0]][y^1];
			dp[i][y]=a*x+b+pre[i]*x;
			par[i][j]=cht[0];
			while(cht.size()>1 && !cmp(cht[cht.size()-2],cht.back(),i,y^1))cht.pop_back();
			cht.push_back(i);
			
		}//cout<<'\n';
		cht.clear();
	}
	for(int i=1;i<n;i++){
		int y=k&1;
		if(dp[i][y]>=dp[ans][y])ans=i;
	}
	cout<<dp[ans][k&1]<<'\n';
	vector<int>v;
	while(ans!=0){
		v.push_back(ans);
		ans=par[ans][k];
		k--;
	}
	reverse(v.begin(),v.end());
	for(auto i:v){
		cout<<i<<" ";
	}
	return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 4444 KB contestant found the optimal answer: 999 == 999
3 Correct 1 ms 2392 KB contestant found the optimal answer: 0 == 0
4 Incorrect 1 ms 4444 KB contestant didn't find the optimal answer: 1542522 < 1542524
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB contestant didn't find the optimal answer: 1092244 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB contestant didn't find the optimal answer: 407161746 < 610590000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB contestant didn't find the optimal answer: 20166072 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10588 KB contestant didn't find the optimal answer: 1197227808 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 83464 KB contestant didn't find the optimal answer: 13199711688 < 19795776960
2 Halted 0 ms 0 KB -