Submission #167099

#	Time	Username	Problem	Language	Result	Execution time	Memory
167099		Hideo	Divide and conquer (IZhO14_divide)	C++14	100 / 100	127 ms	9040 KiB

divide

// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123

const int N = 2e5 + 7;
const int INF = 1e9 + 7;

pair < ll, ll > pr[N];
ll x[N], g[N], e[N];
ll ans;
int sf[N];
int n;

void divide (int l, int r){
    if (l > r)
        return;
    int mid = (l + r) >> 1, left;
    left = mid;
    vector < pair < ll, int > > vec;
    for (int i = mid; i <= r; i++)
        vec.pb(mk(pr[i].sc - pr[mid - 1].sc + (x[mid] - x[mid - 1]), i));
    sort(all(vec));
    sf[vec.size()] = 0;
    for (int i = vec.size() - 1; i >= 0; i--)
        sf[i] = max(sf[i + 1], vec[i].sc);

    for (int left = mid; left >= l; left--){
        ll cost = pr[mid].sc - pr[left - 1].sc + (x[left] - x[left - 1]) - e[mid];
        int right = lower_bound(all(vec), mk(-cost, 0)) - vec.begin();
        ans = max(ans, pr[sf[right]].fr - pr[left - 1].fr);
    }
    divide(l, mid - 1);
    divide(mid + 1, r);
}

main(){ // If you don't know what to do, check the text box at the bottom
    cin >> n;
    for (int i = 1; i <= n; i++){
        scanf("%lld%lld%lld", &x[i], &g[i], &e[i]);
        pr[i].fr = pr[i - 1].fr + g[i];
        pr[i].sc = (pr[i - 1].sc + e[i]) - (x[i] - x[i - 1]);
    }
    divide(1, n);
    cout << ans << endl;
}

/*
    Totally not inspired by BenQ's template
    Things you should do:
    1. Look for stupid typos in code e.g 1 instead of -1 etc
    2. Check if there is no infinite loops
    3. "Measure twice, cut once"
    4. Stay focused
*/

Compilation message (stderr)

divide.cpp: In function 'void divide(int, int)':
divide.cpp:33:29: warning: variable 'left' set but not used [-Wunused-but-set-variable]
     int mid = (l + r) >> 1, left;
                             ^~~~
divide.cpp: At global scope:
divide.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){ // If you don't know what to do, check the text box at the bottom
      ^
divide.cpp: In function 'int main()':
divide.cpp:55:14: 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], &e[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52