oj.uz

Submission #195614

# Submission time Handle Problem Language Result Execution time Memory
195614 2020-01-16T16:09:25 Z jovan_b Divide and conquer (IZhO14_divide) C++17
100 / 100
 57 ms 7400 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll g[100005];
ll x[100005];
ll d[100005];
ll xx[100005];

int main(){
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    vector <pair <ll, int>> tren;
    ll sum = 0;
    for(int i=1; i<=n; i++){
        cin >> xx[i] >> g[i] >> d[i];
        x[i] = xx[i]-xx[1];
        g[i] += g[i-1];
        d[i] += d[i-1];
        sum = max(sum, g[i]-g[i-1]);
        int l=0, r=tren.size()-1, j=i;
        while(l <= r){
            int mid = (l+r)/2;
            if(tren[mid].first-x[i]+d[i] >= 0){
                r = mid-1;
                j = mid;
            }
            else l = mid+1;
        }
        if(j < tren.size()) sum = max(sum, g[i]-g[tren[j].second-1]);
        if(tren.empty() || tren.back().first < x[i]-d[i-1]) tren.push_back({x[i]-d[i-1], i});
    }
    cout << sum << "\n";
    return 0;
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(j < tren.size()) sum = max(sum, g[i]-g[tren[j].second-1]);
            ~~^~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 436 KB Output is correct
7 Correct 13 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 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 248 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 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 3 ms 404 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 5 ms 888 KB Output is correct
12 Correct 5 ms 760 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 18 ms 888 KB Output is correct
4 Correct 22 ms 2936 KB Output is correct
5 Correct 27 ms 3192 KB Output is correct
6 Correct 56 ms 6492 KB Output is correct
7 Correct 39 ms 5368 KB Output is correct
8 Correct 39 ms 5340 KB Output is correct
9 Correct 34 ms 5112 KB Output is correct
10 Correct 45 ms 6000 KB Output is correct
11 Correct 57 ms 7400 KB Output is correct
12 Correct 51 ms 7400 KB Output is correct