# Untitled

unknown
plain_text
3 months ago
1.2 kB
2
Indexable
Never
```#include <iostream>
using namespace std;
#define INT_MAX 999999999

int m, d; // m: max energy; d: distance;
int runType[5][3]; // runType[i][0] : minutes; runType[i][1] : seconds; runType[i][2] : energy;
int dp[45][605];

int solve(int dist, int energy) {
if (dist == 0) {
if (energy >= 0) {
return 0;
}
else return INT_MAX;
}
if (energy < 0) return INT_MAX;
if (dp[dist][energy] != -1) return dp[dist][energy];
int ans = INT_MAX;
for (int i = 0; i < 5; i++) {
int tmp = solve(dist-1,energy-runType[i][2]) + (runType[i][0]*60+runType[i][1]);
ans = tmp < ans ? tmp : ans;
}
dp[dist][energy] = ans;
return ans;
}

int main() {
freopen("input.txt","r",stdin);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> m >> d;
for (int i = 0; i < 5; i++) {
cin >> runType[i][0] >> runType[i][1] >> runType[i][2];
}
// Can use memset(dp,-1,sizeof(dp)); instead but sever not allow
for (int i = 0; i < 45; i++) {
for (int j = 0; j < 605; j++) {
dp[i][j] = -1;
}
}
int res = solve(d,m);
cout << "Case #" << tc << endl;
if (res == INT_MAX) cout << -1 << endl;
else cout << res / 60 << " " << res % 60 << endl;
}
return 0;
}

```