제출 #382128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382128		mohamedsobhi777	금 캐기 (IZhO14_divide)	C++14	100 / 100	46 ms	4020 KiB

divide

#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 1e9 + 7;

int n;
ll g[N], e[N];
ll x[N];

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n;
       ll ans = 0;
       for (int i = 0; i < n; ++i)
       {
              cin >> x[i] >> g[i] >> e[i];
              ans = max(ans, g[i]);
       }
       for (int i = 1; i < n; ++i)
       {
              g[i] += g[i - 1];
              e[i] += e[i - 1];
       }

       vector<int> qu;

       qu.pb(0);

       auto get = [&](int a) -> ll {
              return x[a] - (a ? e[a - 1] : 0);
       };
       for (int i = 1; i < n; ++i)
       {
              ll mv = get(i) - e[i] + e[i - 1];
              int my_cover = partition_point(all(qu), [&](int j) {
                                    return get(j) < mv;
                             }) -
                             qu.begin();
              if (my_cover < sz(qu))
              {
                     int j = qu[my_cover];
                     ans = max(ans, g[i] - (j ? g[j - 1] : 0));
              }
              if (get(i) > get(qu.back()))
              {
                     qu.push_back(i);
              }
       }
       cout << ans;
       return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52