oj.uz

Submission #161910

# Submission time Handle Problem Language Result Execution time Memory
161910 2019-11-05T09:45:23 Z HungAnhGoldIBO2020 Split the sequence (APIO14_sequence) C++14
0 / 100
 55 ms 9860 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
const int K=101;
int n,pre[K][N];
long long dp[2][N],sum[N];
stack<int> lis;
void solve(int idx,int l,int r,int lef,int rig){
	if(lef>rig){
		return;
	}
	int i,mid=(lef+rig)>>1,max1=-1;
	for(i=min(mid-1,r);i>=l;i--){
		if(max1<dp[(idx+1)&1][i]+(sum[mid]-sum[i])*(sum[n]-sum[mid])){
			max1=dp[(idx+1)&1][i]+(sum[mid]-sum[i])*(sum[n]-sum[mid]);
			pre[idx][mid]=i;
		}
	}
	dp[idx&1][mid]=max1;
	solve(idx,l,pre[idx][mid],lef,mid-1);
	solve(idx,pre[idx][mid],r,mid+1,rig);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int i,j,k,l,num;
	cin>>n>>num;
	for(i=1;i<=n;i++){
		cin>>j;
		sum[i]=sum[i-1]+j;
	}
	for(i=1;i<=n;i++){
		dp[1][i]=(sum[n]-sum[i])*sum[i];
		pre[1][i]=i;
	}
	for(i=2;i<=num;i++){
		solve(i,i-1,n-1,i,n-1);
	}
	j=n;
	for(i=num;i<=n;i++){
		if(dp[num&1][j]<dp[num&1][i]){
			j=i;
		}
	}
	cout<<dp[num&1][j]<<'\n';
	for(i=num;i>0;i--){
		lis.push(j);
		j=pre[i][j];
	}
	while(lis.size()){
		cout<<lis.top()<<' ';
		lis.pop();
	}
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:26:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,num;
          ^
sequence.cpp:26:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,num;
            ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB contestant found the optimal answer: 108 == 108
2 Correct 5 ms 376 KB contestant found the optimal answer: 999 == 999
3 Incorrect 2 ms 380 KB Integer 2 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 2 ms 380 KB contestant found the optimal answer: 302460000 == 302460000
3 Incorrect 2 ms 632 KB Integer 0 violates the range [1, 49]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 2 ms 376 KB contestant found the optimal answer: 311760000 == 311760000
3 Runtime error 7 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 2 ms 380 KB contestant found the optimal answer: 140412195 == 140412195
3 Runtime error 11 ms 2172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 4 ms 760 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Runtime error 55 ms 9860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 4088 KB declared answer doesn't correspond to the split scheme: declared = 2147413813, real = 10737348405
2 Halted 0 ms 0 KB -