#include <bits/stdc++.h>
using namespace std;
#define _LOCAL 0
typedef long long ll;
#define inf ll(1e18)
typedef pair<ll, ll> p2;
typedef vector<ll> vi;
typedef vector<p2> vp2;
typedef vector<vp2> vvp2;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
#define rep(var, high) for (int var = 0; var < high; var++)
// What's the max score we can enter column col with given that the previous col prevcol high
ll solve(int col, int prevcol, int prevprevcol, ll score, vvp2& fishes, vvvi& dp)
{
if (col >= fishes.size()) return score;
ll& v = dp[col][prevcol + 1][prevprevcol + 1];
if (v != -1) return score + v;
ll ret = score;
ll scorediff = 0;
int curcolpointer = 0;
int prevcolpointer = 0;
int nextcolpointer = 0;
// TODO: add 0 transition
ret = max(ret, solve(col + 1, -1, prevcol, score, fishes, dp));
// Build bridge to fishes[col+1][i].height
for (int i = 0; i < dp[0].size() - 1; i++)
{
// Add score if not taken
while (col > 0 && prevcolpointer < fishes[col - 1].size() && fishes[col - 1][prevcolpointer].first <= i)
{
if (fishes[col - 1][prevcolpointer].first > prevcol && fishes[col - 1][prevcolpointer].first > prevprevcol) scorediff += fishes[col - 1][prevcolpointer].second;
prevcolpointer++;
}
// Lose score in current column
// First statement: only lose score for mated ones
while (i <= prevcol && curcolpointer < fishes[col].size() && fishes[col][curcolpointer].first <= i)
{
scorediff -= fishes[col][curcolpointer].second;
curcolpointer++;
}
if (col + 1 < fishes.size() && nextcolpointer < fishes[col + 1].size() && fishes[col + 1][nextcolpointer].first <= i)
{
scorediff += fishes[col + 1][nextcolpointer].second;
nextcolpointer++;
}
ret = max(ret, solve(col + 1, i, prevcol, score + scorediff, fishes, dp));
}
v = ret - score;
return ret;
}
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y, std::vector<int> w)
{
int maxy = 0;
vvp2 fishes(n);
rep(i, m)
{
maxy = max(maxy, y[i]);
fishes[x[i]].emplace_back(y[i], w[i]);
}
rep(i, n) sort(fishes[i].begin(), fishes[i].end());
vvvi dp(n, vvi(maxy + 4, vi(maxy + 4, -1)));
return solve(0, -1, -1, 0, fishes, dp);
}
#if _LOCAL
int main()
{
int n, m;
cin >> n >> m;
vector<int> x(m);
vector<int> y(m);
vector<int> w(m);
rep(i, m)
{
cin >> x[i];
cin >> y[i];
cin >> w[i];
}
cout << max_weights(n, m, x, y, w);
}
#endif
Compilation message
fish.cpp: In function 'll solve(int, int, int, ll, vvp2&, vvvi&)':
fish.cpp:18:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | if (col >= fishes.size()) return score;
| ~~~~^~~~~~~~~~~~~~~~
fish.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i = 0; i < dp[0].size() - 1; i++)
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp:38:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | while (col > 0 && prevcolpointer < fishes[col - 1].size() && fishes[col - 1][prevcolpointer].first <= i)
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:46:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | while (i <= prevcol && curcolpointer < fishes[col].size() && fishes[col][curcolpointer].first <= i)
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if (col + 1 < fishes.size() && nextcolpointer < fishes[col + 1].size() && fishes[col + 1][nextcolpointer].first <= i)
| ~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp:52:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if (col + 1 < fishes.size() && nextcolpointer < fishes[col + 1].size() && fishes[col + 1][nextcolpointer].first <= i)
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
775 ms |
2097152 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
793 ms |
2097152 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
50252 KB |
Output is correct |
2 |
Correct |
111 ms |
50376 KB |
Output is correct |
3 |
Correct |
155 ms |
48948 KB |
Output is correct |
4 |
Correct |
136 ms |
52508 KB |
Output is correct |
5 |
Correct |
170 ms |
55884 KB |
Output is correct |
6 |
Correct |
178 ms |
56528 KB |
Output is correct |
7 |
Correct |
159 ms |
56644 KB |
Output is correct |
8 |
Correct |
175 ms |
56636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
10 ms |
724 KB |
Output is correct |
11 |
Correct |
6 ms |
468 KB |
Output is correct |
12 |
Correct |
10 ms |
800 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
4 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
10 ms |
724 KB |
Output is correct |
11 |
Correct |
6 ms |
468 KB |
Output is correct |
12 |
Correct |
10 ms |
800 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
4 ms |
596 KB |
Output is correct |
15 |
Execution timed out |
1099 ms |
218804 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
10 ms |
724 KB |
Output is correct |
11 |
Correct |
6 ms |
468 KB |
Output is correct |
12 |
Correct |
10 ms |
800 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
4 ms |
596 KB |
Output is correct |
15 |
Execution timed out |
1099 ms |
218804 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
50252 KB |
Output is correct |
2 |
Correct |
111 ms |
50376 KB |
Output is correct |
3 |
Correct |
155 ms |
48948 KB |
Output is correct |
4 |
Correct |
136 ms |
52508 KB |
Output is correct |
5 |
Correct |
170 ms |
55884 KB |
Output is correct |
6 |
Correct |
178 ms |
56528 KB |
Output is correct |
7 |
Correct |
159 ms |
56644 KB |
Output is correct |
8 |
Correct |
175 ms |
56636 KB |
Output is correct |
9 |
Runtime error |
771 ms |
2097152 KB |
Execution killed with signal 9 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
775 ms |
2097152 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |