提出 #41097423

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

ll op(ll a, ll b){ return max(a, b); }
ll e(){ return -1; }

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  // 入力
  int N;
  cin >> N;
  vector<int> r(N), c(N), x(N);

  map<int, int> mpr, mpc;
  
  for (int i = 0; i < N; i++){
    cin >> r[i] >> c[i] >> x[i];
    mpr[r[i]] = 0;
    mpc[c[i]] = 0;
  }

  // 座標圧縮
  int mr = 0;
  for (auto &p : mpr){ p.second = mr++; }
  int mc = 0;
  for (auto &p : mpc){ p.second = mc++; }

  // 各行、列ごとの和
  vector<ll> sumr(mr), sumc(mc);

  // 各行にある点のリスト
  vector<vector<pair<int, int>>> vec(mr);

  for (int i = 0; i < N; i++){
    int ri = mpr[r[i]];
    int ci = mpc[c[i]];
    sumr[ri] += x[i];
    sumc[ci] += x[i];
    vec[ri].emplace_back(ci, x[i]);
  }

  // Solve
  segtree<ll, op, e> seg(mc);
  for (int i = 0; i < mc; i++){
    seg.set(i, sumc[i]);
  }

  ll ans = 0;
  for (int i = 0; i < mr; i++){
    for (auto p : vec[i]){
      auto [cj, xj] = p;
      seg.set(cj, seg.get(cj) - xj);
    }
    chmax(ans, sumr[i] + seg.all_prod());
    for (auto p : vec[i]){
      auto [cj, xj] = p;
      seg.set(cj, seg.get(cj) + xj);
    }
  }
  
  cout << ans << endl;
  return 0;
}

提出情報

ジャッジ結果