oj.uz

Submission #37759

# Submission time Handle Problem Language Result Execution time Memory
37759 2017-12-28T04:39:31 Z Just_Solve_The_Problem Divide and conquer (IZhO14_divide) C++11
17 / 100
 1000 ms 10608 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = (int)1e5 + 7;

ll x[N], g[N], d[N];

struct T {
    ll sd, sg;
    T () {
        sd = sg = 0;
    }
    T (ll x, ll y) {
        sg = x;
        sd = y;
    }
};

T tree[N * 4];

void build (int v, int l, int r) {
    if (l == r) {
        tree[v].sg = g[l];
        tree[v].sd = d[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build (v + v, l, mid);
    build (v + v + 1, mid + 1, r);
    tree[v].sg = tree[v + v].sg + tree[v + v + 1].sg;
    tree[v].sd = tree[v + v].sd + tree[v + v + 1].sd;
}

T get (int v, int l, int r, int tl, int tr) {
    if (l <= tl && tr <= r) {
        return tree[v];
    }
    if (tl > r || tr < l) {
        return T(0, 0);
    }
    int mid = (tl + tr) >> 1;
    T a = get(v + v, l, r, tl, mid);
    T b = get(v + v + 1, l, r, mid + 1, tr);
    return T (a.sg + b.sg, a.sd + b.sd);
}

main () {
    int n; scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%lld %lld %lld", x + i, g + i, d + i);
    }
    build(1, 1, n);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            T a = get(1, i, j, 1, n);
            if (x[j] - x[i] <= a.sd) {
                ans = max(ans, a.sg);
            }
        }
    }
    cout << ans;
}

Compilation message

divide.cpp:50:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
divide.cpp: In function 'int main()':
divide.cpp:51: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:53: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 10608 KB Output is correct
2 Correct 0 ms 10608 KB Output is correct
3 Correct 0 ms 10608 KB Output is correct
4 Correct 0 ms 10608 KB Output is correct
5 Correct 0 ms 10608 KB Output is correct
6 Correct 0 ms 10608 KB Output is correct
7 Correct 0 ms 10608 KB Output is correct
8 Correct 0 ms 10608 KB Output is correct
9 Correct 3 ms 10608 KB Output is correct
10 Correct 0 ms 10608 KB Output is correct
11 Correct 3 ms 10608 KB Output is correct
12 Correct 3 ms 10608 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10608 KB Output is correct
2 Correct 3 ms 10608 KB Output is correct
3 Correct 19 ms 10608 KB Output is correct
4 Correct 36 ms 10608 KB Output is correct
5 Correct 56 ms 10608 KB Output is correct
6 Correct 106 ms 10608 KB Output is correct
7 Correct 79 ms 10608 KB Output is correct
8 Correct 73 ms 10608 KB Output is correct
9 Correct 179 ms 10608 KB Output is correct
10 Correct 313 ms 10608 KB Output is correct
11 Execution timed out 1000 ms 10608 KB Execution timed out
12 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 10608 KB Execution timed out
2 Halted 0 ms 0 KB -