#include <bits/stdc++.h>
using namespace std;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)
template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
long long max_weights(int numCol, int numCatfish, vector <int> rows, vector <int> cols, vector <int> weights) {
vector <vector <pair <int, long long>>> atCol(numCol);
REP(i, numCatfish) {
atCol[cols[i]].push_back(make_pair(rows[i], weights[i]));
}
REP(i, numCol) {
sort(ALL(atCol[i]));
atCol[i].emplace_back(numCol, 0);
long long pre = 0;
for (auto &[_, x] : atCol[i]) {
x += pre;
pre = x;
}
}
auto prefix_sum = [&] (int i, int cur) -> long long {
auto it = lower_bound(ALL(atCol[i]), make_pair(cur, -1ll));
if(it != atCol[i].begin()) return prev(it) -> second;
return 0;
};
vector <vector <vector <long long>>> dp(numCol, vector <vector <long long>>(2));
REP(i, numCol) {
dp[i][0].resize((int) atCol[i].size(), 0);
dp[i][1].resize((int) atCol[i].size(), 0);
long long Max = 0;
if(i == 0) continue;
for (int cur = (int) atCol[i].size() - 1, pre = (int) atCol[i - 1].size(); cur >= 0; cur--) {
while(pre > 0 && atCol[i - 1][pre - 1].first >= atCol[i][cur].first) {
pre--;
maximize(Max, dp[i - 1][0][pre] + prefix_sum(i, atCol[i - 1][pre].first));
}
maximize(dp[i][0][cur], Max - prefix_sum(i, atCol[i][cur].first));
}
Max = (i > 1 ? max(*max_element(ALL(dp[i - 2][0])), *max_element(ALL(dp[i - 2][1]))) : 0);
for (int cur = 0, pre = -1; cur < (int) atCol[i].size(); ++cur) {
while(pre + 1 < (int) atCol[i - 1].size() && atCol[i - 1][pre + 1].first <= atCol[i][cur].first) {
pre++;
maximize(Max, dp[i - 1][1][pre] - prefix_sum(i - 1, atCol[i - 1][pre].first));
}
// cout << cur << '\n';
maximize(dp[i][1][cur], Max + prefix_sum(i - 1, atCol[i][cur].first));
}
}
return max(*max_element(ALL(dp[numCol - 1][0])), *max_element(ALL(dp[numCol - 1][1])));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
22092 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '24806557567238' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
107 ms |
26444 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '46804015619258' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
20564 KB |
Output is correct |
| 2 |
Correct |
31 ms |
20660 KB |
Output is correct |
| 3 |
Incorrect |
50 ms |
22484 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638' |
| 4 |
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 |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 9 |
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 |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 9 |
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 |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
20564 KB |
Output is correct |
| 2 |
Correct |
31 ms |
20660 KB |
Output is correct |
| 3 |
Incorrect |
50 ms |
22484 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
22092 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '24806557567238' |
| 2 |
Halted |
0 ms |
0 KB |
- |
