Submission #37759

#	Time	Username	Problem	Language	Result	Execution time	Memory
37759		Just_Solve_The_Problem	Divide and conquer (IZhO14_divide)	C++11	17 / 100	1000 ms	10608 KiB

divide

#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 (stderr)

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 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52