#include <bits/stdc++.h>
#ifndef LOCAL
#include <fish.h>
#endif // LOCAL
using namespace std;
#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true; return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true; return false;
}
using ll = long long;
using ld = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }
const int MAX = 3e5 + 5;
int n, m;
struct fish{
int x, y, w;
} fishes[MAX];
namespace subtask1{
bool check(){
rep(i, 0, m) if(fishes[i].x& 1) return false;
return true;
}
ll solve(){
ll sum = 0;
rep(i, 0, m){
if((i > 0) || (i < n - 1)){
sum += fishes[i].w;
}
}
return sum;
}
}
namespace subtask2{
bool check(){
for(int i = 0; i < m; ++i){
if(fishes[i].x > 1) return false;
}
return true;
}
ll sum[3][MAX];
ll f[3][MAX], g[3][MAX];
ll solve(){
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
rep(i, 0, m){
sum[fishes[i].x][fishes[i].y] += fishes[i].w;
}
rep(i, 0, 2){
rep(j, 0, n){
sum[i][j] += (j > 0 ? sum[i][j - 1] : 0);
}
}
ll ans = max(sum[0][n - 1], sum[1][n - 1]);
if(n > 2){
rep(i, 0, n){
maximize(ans, sum[1][n - 1] - sum[1][i] + sum[0][i]);
}
}
return ans;
}
}
namespace subtask3{
bool check(){
rep(i, 0, m){
if(fishes[i].y > 0) return false;
}
return true;
}
ll dp[MAX], s[MAX];
ll solve(){
rep(i, 0, m) s[fishes[i].x] = fishes[i].w;
dp[0] = 0;
ll res = 0;
rep(i, 1, n){
dp[i] = max(dp[i - 1], s[i - 1]);
if(i >= 2) maximize(dp[i], dp[i - 2] + s[i - 1]);
if(i >= 3) maximize(dp[i], dp[i - 3] + s[i - 2] + s[i - 1]);
maximize(res, dp[i] + s[i + 1]);
}
return res;
}
}
namespace subtask45{
bool check(){
return n <= 300;
}
ll pref[305][305];
ll solve(){
rep(i, 0, m){
pref[fishes[i].x + 1][fishes[i].y + 1] += fishes[i].w;
}
FOR(i, 1, n){
FOR(j, 1, n){
pref[i][j] += pref[i][j - 1];
}
}
const ll inf = 1e18;
vector<vector<ll>> f(n + 1, vector<ll>(n + 1, -inf));
vector<vector<ll>> g(n + 1, vector<ll>(n + 1, -inf));
/*
let f[c][r] = the maximum sum of weights if we put a pier (c, r) but we don't consider the fishes (c, r') with r' >= r
g[c][r] = the maximum sum of weights if we put a pier (c, r) but we consider the fishes (c, r') with r' >= r
let R[i] the height of pier on column c the we put
consider when R[i - 1] < R[i] -> it contributes to f[c][r]
consider when R[i - 1] > R[i] -> it contributes to g[c][r]
when calculating f[c][r] :
- consider R[i - 2] > R[i - 1] < R[i]
- consider R[i - 2] < R[i - 1] < R[i]
*/
FOR(i, 0, n){
f[1][i] = g[1][i] = 0;
}
FOR(c, 2, n){
FOR(r, 0, n){
if(r == 0){
maximize(f[c][r], g[c - 1][r]);
}
FOR(k, 0, r){
maximize(f[c][r], f[c - 1][k] + pref[c - 1][r] - pref[c - 1][k]);
// cout << dbg(c) << dbg(r) << dbg(f[c - 1][k] + pref[c - 1][r] + pref[c - 1][k]) << '\n';
}
if(c > 2 && r > 0){
FOR(k, 0, n){
maximize(f[c][r], max(f[c - 2][r], g[c - 2][r]) + pref[c - 1][max(r, k)]);
// cout << dbg(c) << dbg(r) << dbg(max(f[c - 2][r], g[c - 2][r]) + pref[c - 1][max(r, k)]) << '\n';
}
}
FOR(k, r, n){
maximize(g[c][r], max(f[c - 1][k], g[c - 1][k]) + pref[c][k] - pref[c][r]);
// cout<< dbg(c) << dbg(r) << dbg(max(f[c - 1][k], g[c - 1][k]) + pref[c][k] - pref[c][r]) << '\n';
}
}
}
ll ans = 0;
FOR(c, 1, n){
FOR(r, 1, n){
maximize(ans, max(f[c][r], g[c][r]) + (c < n ? pref[c + 1][r] : 0));
}
}
FOR(i, 1, n){
FOR(j, 1, n){
cout << pref[j][n - i + 1] << " \n"[j == n];
}
}
// cout << "F[r][c] : \n";
// FOR(i, 1, n){
// FOR(j, 1, n){
// cout << f[j][n - i + 1] << " \n"[j == n];
// }
// }
//
// cout << '\n' << "G[r][c] : \n";
// FOR(i, 1, n){
// FOR(j, 1, n){
// cout << g[j][n - i + 1] << " \n"[j == n];
// }
// }
// cerr << "subtask 4, 5 : ";
return ans;
}
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
n = N;
m = M;
rep(i, 0, M) fishes[i] = {X[i], Y[i], W[i]};
// if(subtask1::check()) return subtask1::solve();
// if(subtask2::check()) return subtask2::solve();
// if(subtask3::check()) return subtask3::solve();
if(subtask45::check()) return subtask45::solve();
return -1;
}
#ifdef LOCAL
int main(){
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
int N, M;
cin >> N >> M;
vector<int> X(M), Y(M), W(M);
rep(i, 0, M){
cin >> X[i] >> Y[i] >> W[i];
}
cout << max_weights(N, M, X, Y, W) << '\n';
}
#endif // LOCAL
Compilation message
fish.cpp: In function 'bool minimize(T&, const T&)':
fish.cpp:18:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
18 | if(a > b) return a = b, true; return false;
| ^~
fish.cpp:18:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
18 | if(a > b) return a = b, true; return false;
| ^~~~~~
fish.cpp: In function 'bool maximize(T&, const T&)':
fish.cpp:23:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
23 | if(a < b) return a = b, true; return false;
| ^~
fish.cpp:23:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
23 | if(a < b) return a = b, true; return false;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
6224 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '-1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2552 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '-1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '-1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
6224 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '-1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
