oj.uz

답안 #654510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654510 2022-10-31T14:31:15 Z ayalla 금 캐기 (IZhO14_divide) C++14
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long int
#define endl '\n'
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pi>
#define fir first
#define sec second
#define MAXN 100005
#define mod 1000000007

struct item
{
  int sg, pref, suf, sum;
};

vector<item> seg;
vector<int> aux;

item single(int x)
{
  return {max(0ll, x), max(0ll, x), max(0ll, x), x};
}
item neutral()
{
  return {0, 0, 0, 0};
}
item merge(item a, item b)
{
  item ret;
  ret.sg = max({a.sg, b.sg, a.suf + b.pref});
  ret.pref = max(a.pref, a.sum + b.pref);
  ret.suf = max(b.suf, b.sum + a.suf);
  ret.sum = a.sum + b.sum;
  return ret;
}
void update(int i, int l, int r, int q, int x)
{
  if (l == r)
  {
    seg[i] = single(x);
    return;
  }
  int mid = (l + r) >> 1;
  if (q <= mid)
    update(i << 1, l, mid, q, x);
  else
    update((i << 1) | 1, mid + 1, r, q, x);
  seg[i] = merge(seg[i << 1], seg[(i << 1) | 1]);
}
item query(int l, int r, int ql, int qr, int i)
{
  int mid = (l + r) >> 1;
  if (l > r || l > qr || r < ql)
    return neutral();
  if (l >= ql && r <= qr)
    return seg[i];
  return merge(query(l, mid, ql, qr, i << 1), query(mid + 1, r, ql, qr, (i << 1) | 1));
}
void build(int l, int r, int i)
{
  if (l == r)
  {
    seg[i] = single(aux[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, i << 1);
  build(mid + 1, r, (i << 1) | 1);
  seg[i] = merge(seg[i << 1], seg[(i << 1) | 1]);
}
signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<pii> v(n);
  int ans = 0;
  for (int i = 0; i < n; i++)
  {
    cin >> v[i].fir >> v[i].sec.fir >> v[i].sec.sec;
    ans = max(ans, v[i].sec.fir);
  }
  sort(v.begin(), v.end());
  aux.assign(n, 0);
  for (int i = 1; i < n; i++)
  {
    aux[i] = v[i].sec.fir - (v[i].fir - v[i - 1].fir);
  }
  cout << ans << endl;
  return 0;
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -