oj.uz

Submission #167099

# Submission time Handle Problem Language Result Execution time Memory
167099 2019-12-05T17:48:23 Z Hideo Divide and conquer (IZhO14_divide) C++14
100 / 100
 127 ms 9040 KB 
// 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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 14 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 6 ms 760 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 9 ms 1052 KB Output is correct
3 Correct 10 ms 1144 KB Output is correct
4 Correct 43 ms 4264 KB Output is correct
5 Correct 48 ms 4608 KB Output is correct
6 Correct 99 ms 9040 KB Output is correct
7 Correct 85 ms 7972 KB Output is correct
8 Correct 86 ms 8196 KB Output is correct
9 Correct 85 ms 7788 KB Output is correct
10 Correct 127 ms 7784 KB Output is correct
11 Correct 87 ms 8296 KB Output is correct
12 Correct 94 ms 8516 KB Output is correct