oj.uz

답안 #37770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37770 2017-12-28T05:20:35 Z Talant 금 캐기 (IZhO14_divide) C++14
100 / 100
 433 ms 56704 KB 
#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e18 + 7;
const ll N = (ll)1e6 + 7;

ll n;
ll x[N],g[N],d[N];
ll p[N],res[N],mx,a[N],t[N];

void build (ll v = 1,ll tl = 1,ll tr = n) {
        if (tl == tr)
                t[v] = a[tl];
        else {
                ll tm = (tl + tr) >> 1;

                build (v * 2,tl,tm);
                build (v * 2 + 1,tm + 1,tr);

                t[v] = max(t[v * 2],t[v * 2 + 1]);
        }
}

ll get (ll l,ll r,ll v = 1,ll tl = 1,ll tr = n) {
        if (r < tl || l > tr)
                return -inf;
        if (l <= tl && tr <= r)
                return t[v];

        ll tm = (tl + tr) >> 1;

        return max(get(l,r,v * 2,tl,tm),get(l,r,v * 2 + 1,tm + 1,tr));
}

int main () {
        cin >> n;

        for (ll i = 1; i <= n; i ++) {
                cin >> x[i] >> g[i] >> d[i];
                p[i] = p[i - 1] + d[i];
                res[i] = res[i - 1] + g[i];
                a[i] = p[i] - x[i];
        }

        build ();

        for (ll i = 1; i <= n; i ++) {
                ll l = i,r = n;

                while (r - l > 1) {
                        ll m = (r + l) >> 1;

                        if (get(m,n) >= p[i - 1] - x[i])
                                l = m;
                        else
                                r = m;
                }
                if (get(r,n) >= p[i - 1] - x[i])
                         l = r;

                mx = max(mx,res[l] - res[i - 1]);
        }

        cout << mx << endl;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 56704 KB Output is correct
2 Correct 0 ms 56704 KB Output is correct
3 Correct 0 ms 56704 KB Output is correct
4 Correct 0 ms 56704 KB Output is correct
5 Correct 0 ms 56704 KB Output is correct
6 Correct 0 ms 56704 KB Output is correct
7 Correct 0 ms 56704 KB Output is correct
8 Correct 0 ms 56704 KB Output is correct
9 Correct 0 ms 56704 KB Output is correct
10 Correct 0 ms 56704 KB Output is correct
11 Correct 0 ms 56704 KB Output is correct
12 Correct 0 ms 56704 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 56704 KB Output is correct
2 Correct 0 ms 56704 KB Output is correct
3 Correct 0 ms 56704 KB Output is correct
4 Correct 0 ms 56704 KB Output is correct
5 Correct 0 ms 56704 KB Output is correct
6 Correct 3 ms 56704 KB Output is correct
7 Correct 3 ms 56704 KB Output is correct
8 Correct 0 ms 56704 KB Output is correct
9 Correct 0 ms 56704 KB Output is correct
10 Correct 3 ms 56704 KB Output is correct
11 Correct 16 ms 56704 KB Output is correct
12 Correct 13 ms 56704 KB Output is correct

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 56704 KB Output is correct
2 Correct 26 ms 56704 KB Output is correct
3 Correct 43 ms 56704 KB Output is correct
4 Correct 169 ms 56704 KB Output is correct
5 Correct 209 ms 56704 KB Output is correct
6 Correct 419 ms 56704 KB Output is correct
7 Correct 363 ms 56704 KB Output is correct
8 Correct 389 ms 56704 KB Output is correct
9 Correct 353 ms 56704 KB Output is correct
10 Correct 376 ms 56704 KB Output is correct
11 Correct 396 ms 56704 KB Output is correct
12 Correct 433 ms 56704 KB Output is correct