oj.uz

Submission #37851

# Submission time Handle Problem Language Result Execution time Memory
37851 2017-12-28T10:27:49 Z Just_Solve_The_Problem Divide and conquer (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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