Submission #1178055

---

Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;

int n, ma, mb, a[40], b[40], c[40], dp[41][400][400];

void init() {
	for (int k = 0; k < 41; k++) {
		for (int i = 0; i < 401; i++) {
			for (int j = 0; j < 401; j++) {
				dp[k][i][j] = -1;
			}
		}
	}
	dp[0][0][0] = 0;
}

int main() {
	cin >> n >> ma >> mb;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	init();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 401; j++) {
			for (int k = 0; k < 401; k++) {
				if (dp[i][j][k] != -1) {
					if (dp[i + 1][j + a[i]][k + b[i]] == -1 || dp[i + 1][j + a[i]][k + b[i]] > dp[i][j][k] + c[i])
						dp[i + 1][j + a[i]][k + b[i]] = dp[i][j][k] + c[i];
					if (dp[i + 1][j][k] == -1 || dp[i+1][j][k] > dp[i][j][k])
						dp[i + 1][j][k] = dp[i][j][k];
				}
			}
		}
	}
	int ans = -1;
	for (int i = 0; i < 401; i++) {
		for (int j = 0; j < 401; j++) {
			if (dp[n][i][j] != -1 && i*ma == j*mb && dp[n][i][j] != 0) {
				//cout << "a[" << i << "]:" << a[i]<< " b[" << i << "]:" << b[i] << " ma:" << ma << " mb:" << mb << endl;
				if (ans == -1)ans = dp[n][i][j];
				else ans = min(ans, dp[n][i][j]);
			}
		}
	}

	cout << ans << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void init()’:
./Main.cpp:11:21: warning: iteration 400u invokes undefined behavior [-Waggressive-loop-optimizations]
     dp[k][i][j] = -1;
                     ^
./Main.cpp:10:22: note: containing loop
    for (int j = 0; j < 401; j++) {
                      ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:39:18: warning: iteration 400u invokes undefined behavior [-Waggressive-loop-optimizations]
    if (dp[n][i][j] != -1 && i*ma == j*mb && dp[n][i][j] != 0) {
                  ^
./Main.cpp:38:21: note: containing loop
   for (int j = 0; j < 401; j++) {
                     ^
./Main.cpp:27:19: warning: iteration 400u invokes undefined behavior [-Waggressive-loop-optimizations]
     if (dp[i][j][k] != -1) {
                   ^
./Main.cpp:26:22: note: containing loop
    for (int k = 0; k < 401; k++) {
                      ^
cc1plus: warning: iteration 399u invokes undefined behavior [-Waggressive-loop-optimizations]
./Main.cpp:25:21: note: containing loop
   for (int j = 0;...

Judge Result