oj.uz

Submission #112684

# Submission time Handle Problem Language Result Execution time Memory
112684 2019-05-21T12:08:41 Z nafis_shifat Split the sequence (APIO14_sequence) C++14
50 / 100
 2000 ms 24064 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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 384 KB contestant found the optimal answer: 999 == 999
3 Correct 2 ms 256 KB contestant found the optimal answer: 0 == 0
4 Correct 2 ms 384 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 2 ms 384 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 2 ms 256 KB contestant found the optimal answer: 1 == 1
7 Correct 2 ms 384 KB contestant found the optimal answer: 1 == 1
8 Correct 2 ms 384 KB contestant found the optimal answer: 1 == 1
9 Correct 2 ms 256 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 2 ms 384 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 2 ms 256 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 2 ms 256 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 2 ms 256 KB contestant found the optimal answer: 140072 == 140072
14 Correct 2 ms 256 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 2 ms 256 KB contestant found the optimal answer: 805 == 805
16 Correct 2 ms 256 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 2 ms 384 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 2 ms 256 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 2 ms 384 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 2 ms 256 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 2 ms 384 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 2 ms 384 KB contestant found the optimal answer: 933702 == 933702
7 Correct 2 ms 384 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 2 ms 384 KB contestant found the optimal answer: 687136 == 687136
9 Correct 2 ms 384 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 2 ms 384 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 2 ms 356 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 1 ms 768 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 2 ms 384 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 5 ms 640 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 5 ms 768 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 5 ms 768 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 3 ms 512 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 3 ms 384 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 4 ms 512 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 4 ms 384 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 157 ms 2724 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 4 ms 384 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 168 ms 2780 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 144 ms 2380 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 158 ms 2808 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 158 ms 2796 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 38 ms 856 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 71 ms 1400 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 896 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 191 ms 1016 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Execution timed out 2056 ms 24064 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 2057 ms 6656 KB Time limit exceeded
2 Halted 0 ms 0 KB -