oj.uz

답안 #37851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37851 2017-12-28T10:27:49 Z Just_Solve_The_Problem 금 캐기 (IZhO14_divide) C++11
100 / 100
 79 ms 7484 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

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

ll pg[N], pd[N];
ll x[N], g[N], d[N], a[N];
ll suf[N];
ll ans = 0;

main () {
    int n; scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%lld %lld %lld", x + i, g + i, d + i);
        pd[i] = pd[i - 1] + d[i];
        pg[i] = pg[i - 1] + g[i];
        a[i] = pd[i] - x[i];
    }
    suf[n + 1] = -inf;
    for (int i = n; i >= 1; i--) {
        suf[i] = max(suf[i + 1], a[i]);
    }
    for (int i = 1; i <= n; i++) {
        int l = i;
        int r = n;
        while (r - l > 1) {
            int mid = (l + r) >> 1;
            if (suf[mid] >= pd[i - 1] - x[i]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        if (suf[r] >= pd[i - 1] - x[i]) {
            l = r;
        }
        ans = max(ans, pg[l] - pg[i - 1]);
    }
    cout << ans;
}

Compilation message

divide.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
divide.cpp: In function 'int main()':
divide.cpp:16:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf ("%d", &n);
                            ^
divide.cpp:18:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%lld %lld %lld", x + i, g + i, d + i);
                                                      ^

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7484 KB Output is correct
2 Correct 3 ms 7484 KB Output is correct
3 Correct 3 ms 7484 KB Output is correct
4 Correct 23 ms 7484 KB Output is correct
5 Correct 26 ms 7484 KB Output is correct
6 Correct 79 ms 7484 KB Output is correct
7 Correct 63 ms 7484 KB Output is correct
8 Correct 53 ms 7484 KB Output is correct
9 Correct 53 ms 7484 KB Output is correct
10 Correct 59 ms 7484 KB Output is correct
11 Correct 53 ms 7484 KB Output is correct
12 Correct 56 ms 7484 KB Output is correct