# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
135037 | CaroLinda | 수열 (APIO14_sequence) | C++14 | 48 ms | 2296 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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") ;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |