oj.uz

Submission #49803

# Submission time Handle Problem Language Result Execution time Memory
49803 2018-06-03T08:22:12 Z mra2322001 Divide and conquer (IZhO14_divide) C++14
100 / 100
 80 ms 22724 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i=(0); i<n; i++)
#define f1(i, n) for(int i=(1); i<=n; i++)

using namespace std;
typedef long long ll;
const int N = 1e5 + 3;

int n;
ll x[N], g[N], d[N], ma[N], sum[N];

main(){
    ios_base::sync_with_stdio(0);

    cin >> n;
    f1(i, n) cin >> x[i] >> g[i] >> d[i];
    f1(i, n) d[i] += d[i - 1];
    f1(i, n) sum[i] = sum[i - 1] + g[i];
    ma[0] = 1e17;
    f1(i, n){
        ma[i] = d[i - 1] - x[i];
    }
    f1(i, n) ma[i] = min(ma[i], ma[i - 1]);
    ll res = 0;
    f1(i, n){
        ll t = d[i] - x[i];
        int l = 1, r = i - 1, ans = 0;
        while(l <= r){
            int mid = (l + r)/2;
            if(ma[mid] <= t) r = mid - 1, ans = mid;
            else l = mid + 1;
        }
        res = max(res, g[i]);
        if(ans){
            res = max(res, sum[i] - sum[ans - 1]);
        }
    }
    cout << res;
}

Compilation message

divide.cpp:12:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 696 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 3 ms 704 KB Output is correct
5 Correct 3 ms 736 KB Output is correct
6 Correct 4 ms 908 KB Output is correct
7 Correct 3 ms 960 KB Output is correct
8 Correct 3 ms 960 KB Output is correct
9 Correct 3 ms 960 KB Output is correct
10 Correct 3 ms 1032 KB Output is correct
11 Correct 5 ms 1172 KB Output is correct
12 Correct 4 ms 1308 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1436 KB Output is correct
2 Correct 5 ms 1752 KB Output is correct
3 Correct 6 ms 1880 KB Output is correct
4 Correct 22 ms 4512 KB Output is correct
5 Correct 28 ms 5952 KB Output is correct
6 Correct 71 ms 10888 KB Output is correct
7 Correct 59 ms 12704 KB Output is correct
8 Correct 51 ms 14536 KB Output is correct
9 Correct 50 ms 16372 KB Output is correct
10 Correct 50 ms 18228 KB Output is correct
11 Correct 80 ms 20316 KB Output is correct
12 Correct 58 ms 22724 KB Output is correct