oj.uz

답안 #135037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135037 2019-07-23T14:48:24 Z CaroLinda 수열 (APIO14_sequence) C++14
11 / 100
 48 ms 2296 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 108 == 108
2 Correct 2 ms 376 KB contestant found the optimal answer: 999 == 999
3 Incorrect 2 ms 376 KB Integer 0 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1656 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 4 ms 1656 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 48 ms 1656 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 4 ms 1656 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 6 ms 1656 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 5 ms 1656 KB contestant found the optimal answer: 933702 == 933702
7 Correct 17 ms 1656 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 6 ms 1656 KB contestant found the optimal answer: 687136 == 687136
9 Correct 5 ms 1656 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 8 ms 1684 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 2296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -