| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 677187 | Ninja_Kunai | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* Author : Nguyen Tuan Vu
* Created :
**/
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).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, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
void file(){
#define TASK "TASK"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
}
const int N = 1e5 + 5;
const long long INF = 1e18 + 7;
namespace sub6 {
vector <int> coor[N];
vector <long long> f[N], g[N];
vector <pair <int, long long>> sum[N];
long long get_sum(int i, int x) {
//cout << x << '\n';
//for (auto x : sum[i]) cout << x.first << ' ' << x.second << '\n';
int pos = upper_bound(ALL(sum[i]), make_pair(x, INF)) - sum[i].begin() - 1;
//cout << pos << '\n';
if (pos == -1) return 0;
return sum[i][pos].second;
}
long long solve(int n, int m, vector <array <int, 3>> fishes) {
REP(i, m) {
if (fishes[i][0] + 1 > 1) coor[fishes[i][0]].push_back(fishes[i][1] + 1);
if (fishes[i][0] + 1 < n) coor[fishes[i][0] + 2].push_back(fishes[i][1] + 1);
sum[fishes[i][0] + 1].push_back({fishes[i][1] + 1, fishes[i][2]});
}
//return 0;
FOR(i, 1, n) {
coor[i].push_back(0);
sort (ALL(coor[i]));
coor[i].erase(unique(ALL(coor[i])), coor[i].end());
f[i].resize(coor[i].size() + 5, -1);
g[i].resize(coor[i].size() + 5, -1);
sort (ALL(sum[i]));
FOR(j, 1, (int) sum[i].size() - 1) sum[i][j].second += sum[i][j - 1].second;
}
//cout << get_sum(1, 1) << '\n';
//return 0;
//for (auto x : sum[1]) cout << x.first << ' ' << x.second << '\n';
// f : roi
// g : chua
REP(i, coor[1].size()) g[1][i] = 0;
//cout << 1 << ' ';
//return 0;
FOR(i, 2, n) {
REP(k, coor[i - 1].size()) if (f[i - 1][k] != -1 || g[i - 1][k] != -1) {
REP(j, coor[i].size()) if (coor[i - 1][k] <= coor[i][j]) {
// f
if (f[i - 1][k] != -1) maximize(g[i][j], f[i - 1][k]);
// g
if (g[i - 1][k] != -1) {
long long R = get_sum(i - 1, coor[i][j]);
long long L = get_sum(i - 1, coor[i - 1][k]);
//if (i == 2) cout << coor[i - 1][k] << ' ' << coor[i][j] << ' ' << R - L << '\n';
maximize(g[i][j], g[i - 1][k] + R - L);
}
}
else {
// update f
maximize(f[i][j], max(f[i - 1][k], g[i - 1][k]) + get_sum(i, coor[i - 1][k]) - get_sum(i, coor[i][j]));
// update g
maximize(g[i][j], max(f[i - 1][k], g[i - 1][k]));
}
}
if (i > 2) {
REP(k, coor[i - 2].size()) if (f[i - 2][k] != -1 || g[i - 2][k] != -1) {
REP(j, coor[i].size()) {
maximize(g[i][j], max(f[i - 2][k], g[i - 2][k]) + get_sum(i - 1, max(coor[i - 2][k], coor[i][j])));
}
}
}
if (i > 3) {
REP(k, coor[i - 3].size()) if (f[i - 3][k] != -1 || g[i - 3][k] != -1) {
REP(j, coor[i].size()) {
maximize(g[i][j], max(f[i - 3][k], g[i - 3][k]) + get_sum(i - 1, coor[i][j]) + get_sum(i - 2, coor[i - 3][k]));
}
}
}
//cout << i << '\n';
//REP(j, coor[i].size()) {
// cout << j << ' ' << coor[i][j] << ' ' << f[i][j] << ' ' << g[i][j] << '\n';
//}
//cout << '\n';
}
long long ans = 0;
FOR(i, 1, n) REP(j, coor[i].size()) maximize(ans, max(f[i][j], g[i][j]) + get_sum(i + 1, coor[i][j]));
return ans;
}
};
int n, m;
vector <int> X, Y, W;
long long max_weights(int n, int m, vector <int> X, vector <int> Y, vector <int> W) {
vector <array <int, 3>> fishes;
fishes.resize(m + 7);
REP(i, m) fishes[i] = {X[i], Y[i], W[i]};
return sub6::solve(n, m, fishes);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
file();
cin >> n >> m;
X.assign(m + 7, 0);
Y.assign(m + 7, 0);
W.assign(m + 7, 0);
for (int i = 0; i < m; i++) cin >> X[i] >> Y[i] >> W[i];
cout << max_weights(n, m, X, Y, W);
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/