oj.uz

답안 #37768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37768 2017-12-28T05:18:31 Z Talant 금 캐기 (IZhO14_divide) C++14
48 / 100
 416 ms 6312 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 int N = (int)1e5 + 7;

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

void build (int v = 1,int tl = 1,int tr = n) {
        if (tl == tr)
                t[v] = a[tl];
        else {
                int 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 (int l,int r,int v = 1,int tl = 1,int tr = n) {
        if (r < tl || l > tr)
                return -inf;
        if (l <= tl && tr <= r)
                return t[v];

        int 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 (int 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 (int i = 1; i <= n; i ++) {
                int l = i,r = n;

                while (r - l > 1) {
                        int 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 6312 KB Output is correct
2 Correct 0 ms 6312 KB Output is correct
3 Correct 0 ms 6312 KB Output is correct
4 Correct 0 ms 6312 KB Output is correct
5 Correct 0 ms 6312 KB Output is correct
6 Correct 0 ms 6312 KB Output is correct
7 Correct 0 ms 6312 KB Output is correct
8 Correct 0 ms 6312 KB Output is correct
9 Correct 0 ms 6312 KB Output is correct
10 Correct 0 ms 6312 KB Output is correct
11 Correct 0 ms 6312 KB Output is correct
12 Correct 0 ms 6312 KB Output is correct

Subtask #2
31.0 / 31.0

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

Subtask #3
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6312 KB Output is correct
2 Correct 23 ms 6312 KB Output is correct
3 Correct 29 ms 6312 KB Output is correct
4 Correct 179 ms 6312 KB Output is correct
5 Correct 196 ms 6312 KB Output is correct
6 Incorrect 416 ms 6312 KB Output isn't correct
7 Halted 0 ms 0 KB -