oj.uz

Submission #125677

# Submission time Handle Problem Language Result Execution time Memory
125677 2019-07-06T08:03:44 Z minh_star Divide and conquer (IZhO14_divide) C++14
100 / 100
 56 ms 7236 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
long long x[maxn], g[maxn], r[maxn];
typedef pair<long long, int> ii;
ii a[maxn];
int n;
void readinp(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> x[i] >> g[i] >> r[i];
    }
    for (int i = 1; i <= n; i++){
        r[i] = r[i-1] + r[i];
        g[i] = g[i-1] + g[i];
    }
}
void process(){
    for (int i = 1; i <= n; i++){
        a[i].first = r[i-1] - x[i];
        a[i].second = i;
    }
    sort(a+1, a+1+n);
    a[0].second = n + 1;
    for (int i = 1; i <= n; i++){
        a[i].second = min (a[i].second, a[i - 1].second);
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++){
        long long w = r[i] - x[i];
        int l = 1;
        int r = n;
        int res = 1;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (a[mid].first <= w){
                l = mid + 1;
                res = a[mid].second;
            }
            else{
                r = mid - 1;
            }
        }
        ans = max(ans, g[i] - g[res - 1]);
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    readinp();
    process();
    return 0;
}

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 2 ms 376 KB Output is correct
10 Correct 2 ms 380 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 420 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 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 3 ms 504 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 3 ms 504 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 5 ms 632 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 6 ms 952 KB Output is correct
4 Correct 25 ms 3292 KB Output is correct
5 Correct 28 ms 3576 KB Output is correct
6 Correct 56 ms 7236 KB Output is correct
7 Correct 46 ms 6008 KB Output is correct
8 Correct 46 ms 6008 KB Output is correct
9 Correct 44 ms 5880 KB Output is correct
10 Correct 46 ms 5880 KB Output is correct
11 Correct 49 ms 6472 KB Output is correct
12 Correct 51 ms 6520 KB Output is correct