oj.uz

Submission #112683

# Submission time Handle Problem Language Result Execution time Memory
112683 2019-05-21T12:05:51 Z nafis_shifat Split the sequence (APIO14_sequence) C++14
0 / 100
 2000 ms 24056 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> v;
ll cumsum[100008];
int mtg=-1;
ll bs(int l,int r)
{
	int lo=l;
	int hi=r;
	int res=0;
	while(lo<=hi)
	{
		int mid=(lo+hi)/2;
	    
	    int a=cumsum[mid]-cumsum[l-1];
	    int b=cumsum[r]-cumsum[mid-1];
	    if(a>b)
	    {
	    	hi=mid-1;
	    	
		}
		else 
		{
			res=mid;
			lo=mid+1;
		}
		
	}
	mtg=res;	
	ll f= (cumsum[res]-cumsum[l-1])*(cumsum[r]-cumsum[res]);
	if(f==0)mtg=0;
	return f;
}


int main()
{
	int n,k;
	cin>>n>>k;
	
	ll a[n+1];
	cumsum[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cumsum[i]=cumsum[i-1]+a[i];
		
	}
	ll dp[n+1][k+1]={};
	int hld[n+1][k+1]={};
	int next[n+1][k+1];

	for(int i=1;i<n;i++)
	{
	    dp[i][1]=bs(i,n);
	    hld[i][1]=mtg;
	    
	}
	
	for(int j=2;j<=k;j++)
	{
	    for(int i=1;i<=n-j;i++)
	    {
	        for(int l=i;l<=n-j;l++)
	        {
	            ll tmp=(cumsum[l]-cumsum[i-1])*(cumsum[n]-cumsum[l])+dp[l+1][j-1] ;
	            if(tmp  >  dp[i][j])
	            {
	                
	                dp[i][j]=tmp;
	                
	                hld[i][j]=l;
	                
	            }
	        }
	    }
	}
	
	cout<<dp[1][k]<<endl;;
	int l=1;

	for(int i=k;i>0;i--)
	{
	    int t=hld[l][i];
	    if(t==0 || t<=l)
	    {
	        cout<<++l<<" ";
	        
	    }
	    else
	    {
	        cout<<t<<" ";
	        l=hld[l][i]+1;
	    }
	    
	    
	}
	
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:52:6: warning: unused variable 'next' [-Wunused-variable]
  int next[n+1][k+1];
      ^~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB contestant found the optimal answer: 1093956 == 1093956
2 Incorrect 2 ms 256 KB declared answer doesn't correspond to the split scheme: declared = 302460000, real = 202460312
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Integer 200 violates the range [1, 199]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB contestant found the optimal answer: 21503404 == 21503404
2 Incorrect 4 ms 384 KB declared answer doesn't correspond to the split scheme: declared = 140412195, real = 40413179
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 984 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 196 ms 896 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Execution timed out 2025 ms 24056 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 6528 KB Time limit exceeded
2 Halted 0 ms 0 KB -