oj.uz

답안 #17448

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17448 2015-12-13T12:13:10 Z elgun1999 금 캐기 (IZhO14_divide) C++
100 / 100
 68 ms 6408 KB 
#include <iostream>
#include <algorithm>
#include <cstdio>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ll long long

using namespace std;

ll n, x[100005], g[100005], e[100005], p[100005], ans;
pair<ll, ll> d[100005];

int main()
{
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &x[i], &g[i], &e[i]);
        g[i] += g[i - 1], e[i] += e[i - 1];
        d[i] = {e[i] - x[i], i};
    }
    sort(d + 1, d + n + 1);
    for (int i = n; i >= 1; i--)
        p[i] = max(p[i + 1], d[i].s);

    for (int i = 1; i <= n; i++) {
        int a = e[i - 1] - x[i];
        int l = 0, r = n + 1;
        while(r - l > 1) {
            int mid = (l + r) / 2;
            if (d[mid].f >= a) r = mid;
            else l = mid;
        }
        a = p[r];
        ans = max(ans, g[a] - g[i - 1]);
    }
    cout << ans;

    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6408 KB Output is correct
2 Correct 6 ms 6408 KB Output is correct
3 Correct 0 ms 6408 KB Output is correct
4 Correct 21 ms 6408 KB Output is correct
5 Correct 32 ms 6408 KB Output is correct
6 Correct 68 ms 6408 KB Output is correct
7 Correct 46 ms 6408 KB Output is correct
8 Correct 46 ms 6408 KB Output is correct
9 Correct 53 ms 6408 KB Output is correct
10 Correct 55 ms 6408 KB Output is correct
11 Correct 50 ms 6408 KB Output is correct
12 Correct 56 ms 6408 KB Output is correct