제출 #72535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72535		마릴린 희정 (#118)	초코쿠키 기계 (FXCUP3_chocolate)	C++17	0 / 100	3010 ms	1640 KiB

chocolate

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 10005;

int dp[MAXN][30];
int n, k, a[30];

int main(){
	cin >> n >> k;
	for(int i=1; i<=k; i++) cin >> a[i];
	memset(dp, 0x3f, sizeof(dp));
	for(int i=0; i<=k+1; i++) dp[0][i] = 0;
	for(int i=k; i; i--) dp[1][i] = min(a[i], dp[1][i+1]);
	dp[1][0] = 0;
	for(int i=1; i<=n; i++){
		for(int j=k; j; j--){
			for(int l=0; l<=i; l++){
				dp[i][j] = min(dp[i][j], dp[i-l][j+1] + dp[l][0] + l * a[j]);
			}
		}
		for(int j=1; j<i; j++){
			for(int l=1; l<=k; l++){
				dp[i][0] = min(dp[i][0], dp[j][0] + dp[i-j][l + 1] + j * a[l]);
			}
		}
	}
	cout << dp[n][0] << endl;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 55
• Subtask 3: 0 / 17