QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #125961 | #4971. Lecture Allocation | AH_Lusho# | AC ✓ | 56ms | 3680kb | C++14 | 683b | 2023-07-18 01:40:44 | 2023-07-18 01:40:48 |
Judging History
answer
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int l, t;
cin >> l >> t;
vector<vector<int> > cost(t, vector<int>(4));
for (int i = 0; i < t; ++i) {
cin >> cost[i][1] >> cost[i][2] >> cost[i][3];
}
vector<int> dp(l + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= t; ++i) {
for (int j = l; j >= 0; --j) {
for (int k = 1; k <= 3 && k <= j; ++k) {
if (dp[j - k] != INT_MAX) {
dp[j] = min(dp[j], dp[j - k] + cost[i - 1][k]);
}
}
}
}
cout << dp[l] << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3420kb
input:
4 3 11 40 70 20 30 100 20 30 100
output:
60
result:
ok single line: '60'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3420kb
input:
4 3 9 40 70 20 30 100 20 30 100
output:
59
result:
ok single line: '59'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3348kb
input:
1 1 100 101 102
output:
100
result:
ok single line: '100'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
3 1 1 2 100000
output:
100000
result:
ok single line: '100000'
Test #5:
score: 0
Accepted
time: 17ms
memory: 3524kb
input:
5000 1667 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998...
output:
166699999
result:
ok single line: '166699999'
Test #6:
score: 0
Accepted
time: 56ms
memory: 3680kb
input:
5000 5000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998 99999 100000 99998...
output:
166699999
result:
ok single line: '166699999'
Test #7:
score: 0
Accepted
time: 24ms
memory: 3604kb
input:
5000 2500 63409 76090 77141 10973 14546 17373 20557 55409 74972 49257 53665 98448 35253 39186 95166 460 10371 32850 6702 34964 89892 24047 36978 90942 12579 49158 56650 13375 31750 99053 10132 28147 51160 2462 9569 70763 5969 52646 87773 38933 63247 89455 39307 58632 60763 42842 44610 64355 40288 80...
output:
91335442
result:
ok single line: '91335442'
Test #8:
score: 0
Accepted
time: 27ms
memory: 3584kb
input:
5000 2500 1579 21560 57607 24609 75545 77851 7195 77427 81584 10956 35731 85023 5997 18540 39289 80029 96314 99430 3794 16404 97585 49375 50882 55001 16598 27060 54244 1627 20169 28374 53592 81629 96034 40152 47585 59173 17012 37293 50658 40425 49518 71133 55750 59234 77921 46515 66057 73836 2192 30...
output:
89577781
result:
ok single line: '89577781'