#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++)
int N;
// 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 < N+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)
{
N = n;
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, m) sort(fishes[i].begin(), fishes[i].end());
vvvi dp(n, vvi(20, vi(20,-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:20: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]
20 | if (col >= fishes.size()) return score;
| ~~~~^~~~~~~~~~~~~~~~
fish.cpp:40: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]
40 | while (col > 0 && prevcolpointer < fishes[col - 1].size() && fishes[col - 1][prevcolpointer].first <= i)
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:48: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]
48 | while (i <= prevcol && curcolpointer < fishes[col].size() && fishes[col][curcolpointer].first <= i)
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:54:12: 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]
54 | if (col+1<fishes.size()&&nextcolpointer < fishes[col + 1].size() && fishes[col + 1][nextcolpointer].first <= i)
| ~~~~~^~~~~~~~~~~~~~
fish.cpp:54:43: 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]
54 | 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 |
574 ms |
761020 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
81 ms |
17856 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
602 ms |
838320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
| 9 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
| 9 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
| 9 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
602 ms |
838320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
574 ms |
761020 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
