oj.uz

Submission #72535

# Submission time Handle Problem Language Result Execution time Memory
72535 2018-08-26T08:52:40 Z 마릴린 희정(#2180, gs14004, ho94949) Chocolate Cookie Machine (FXCUP3_chocolate) C++17
0 / 100
 3000 ms 1640 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3010 ms 1640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -