Submission #33962

#	Time	Username	Problem	Language	Result	Execution time	Memory
33962		mohammad_kilani	Split the sequence (APIO14_sequence)	C++14	50 / 100	523 ms	3608 KiB

sequence

    #include <bits/stdc++.h>
    using namespace std;
    #define mod 1000000007
    #define oo 2000000000
    const int N = 1010 , K = 201;
    int n , k , arr[N] , sum[N];
    long long dp[N][K];
     
    long long solve(int i,int j){
    	if(j == k) return 0;
    	if(i == n) return -4e18;
    	if(dp[i][j] != -1) return dp[i][j];
    	dp[i][j] = 0 ;
    	for(int l=i;l<n-1;l++){
    		long long cur = sum[l+1] - sum[i];
    		long long cur2 = sum[n] - sum[l+1];
    		long long num = cur * cur2;
    		dp[i][j] = max(dp[i][j],num + solve(l+1,j+1));
    	}
    	return dp[i][j];
    }
     
    void buildpath(int i,int j){
    	if(j == k) return;
    	if(i == n) return;
    	for(int l=i;l<n-1;l++){
    		long long cur1 = sum[l+1] - sum[i];
    		long long cur2 = sum[n] - sum[l+1];
    		long long num = cur1 * cur2;
    		if(num + solve(l+1,j+1) == dp[i][j]){
    			printf("%d ",l+1);
    			buildpath(l+1,j+1);
    			return ;
    		}
    	}
    }
     
     
    int main() {
    	//freopen("in.txt","r",stdin);
    	scanf("%d%d",&n,&k);
    	for(int i=0;i<n;i++){
    		scanf("%d",&arr[i]);
    		sum[i+1] = sum[i] + arr[i];
    	}
    	memset(dp,-1,sizeof(dp));
    	cout << solve(0,0) << endl;
    	buildpath(0,0);
    	cout << endl;
    	return 0;
    }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:41:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d",&n,&k);
                         ^
sequence.cpp:43:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&arr[i]);
                          ^

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29