-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithm.cpp
84 lines (69 loc) · 1.54 KB
/
algorithm.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <limits>
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
typedef std::vector<std::vector<int>> DP;
int search(
std::vector<int> const &v,
DP &dp,
std::vector<int>::const_iterator start,
const int m,
const int k
) {
int idx = start - v.begin();
if (m == 0)
return 0;
else if (start == v.end())
return -1;
else if (dp[idx][m] != -2)
return dp[idx][m];
for (auto j = dp[idx].begin() + m - 1; j != dp[idx].begin(); j--)
if (*j == -1)
return -1;
auto next_best = start;
dp[idx][m] = -1;
for (auto i = start; i != v.end(); i++) {
if (*i != -1) {
int rest = search(v, dp, i + *i, m - 1, k);
if (rest != - 1 && rest + *i > dp[idx][m]) {
dp[idx][m] = rest + *i;
next_best = i;
}
}
}
for (auto i = next_best; i != start; i--) {
dp[i - v.begin()][m] = dp[idx][m];
}
return dp[idx][m];
}
void testcase() {
int n, m, k; std::cin >> n >> m >> k;
std::vector<int> v(n + 1, 0);
DP dp(n + 1, std::vector<int>(m + 1, -2));
for (int i = 1; i <= n; i++) {
int x; std::cin >> x;
v[i] = v[i - 1] + x;
}
for (auto i = v.begin(); i != v.end(); i++) {
auto tgt = std::lower_bound(i + 1, v.end(), *i + k);
if (tgt == v.end() || *tgt != *i + k)
*i = -1;
else
*i = tgt - i;
}
int res = search(v, dp, v.begin(), m, k);
if (res == -1)
std::cout << "fail" << std::endl;
else
std::cout << res << std::endl;
}
int main() {
std::ios_base::sync_with_stdio(false);
int t;
std::cin >> t;
for (int i = 0; i < t; ++i)
testcase();
}