Submission #135037

#	Time	Username	Problem	Language	Result	Execution time	Memory
135037		CaroLinda	Split the sequence (APIO14_sequence)	C++14	11 / 100	48 ms	2296 KiB

sequence

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int inf = 0x3f3f3f3f ;
const int MAXN = 55 ;
const int MAXK = 55 ;

using namespace std ;

int n , k ;
pii cut[MAXN][MAXN][MAXK] ;
ll pref[MAXN] , dp[MAXN][MAXN][MAXK] ;
vector<int> ans ;

ll get(int i , int j) { return pref[j] - pref[i-1] ; }

void buildAns(int ini , int fim, int c)
{
	if(c == 0 ) return ;

	pii now = cut[ini][fim][c] ;

	ans.pb( now.ff ) ;

	buildAns(ini ,now.ff , now.ss ) ;
	buildAns(now.ff+1, fim , c-1-now.ss);
}

int main()
{

	scanf("%d%d", &n , &k ) ;
	lp(i,1,n+1) scanf("%lld", &pref[i] ) ;
	
	lp(i,1,n+1) pref[i] += pref[i-1] ;	

	lp(c,1,k+1)
	{
		lp(i,1,n+1)
			lp(j,i+1,n+1)
			{
				lp(x,i,j)
					lp(y,0,c)
					{
						ll ganho = get(i,x)*get(x+1,j) ;
						ganho += dp[i][x][y] + dp[x+1][j][c-1-y] ;

						if(ganho > dp[i][j][c])
							cut[i][j][c] = mk(x,y) , dp[i][j][c] = ganho ;
					}
			}
	}

	buildAns(1,n,k) ;

	printf("%lld\n", dp[1][n][k]);
	lp(i,0,ans.size()) printf("%d ", ans[i]) ;
	printf("\n") ;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:3:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
sequence.cpp:64:5:
  lp(i,0,ans.size()) printf("%d ", ans[i]) ;
     ~~~~~~~~~~~~~~              
sequence.cpp:64:2: note: in expansion of macro 'lp'
  lp(i,0,ans.size()) printf("%d ", ans[i]) ;
  ^~
sequence.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n , &k ) ;
  ~~~~~^~~~~~~~~~~~~~~~~~
sequence.cpp:40:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  lp(i,1,n+1) scanf("%lld", &pref[i] ) ;
              ~~~~~^~~~~~~~~~~~~~~~~~~

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