oj.uz

Submission #673987

# Submission time Handle Problem Language Result Execution time Memory
673987 2022-12-22T13:45:27 Z Ahmed57 Divide and conquer (IZhO14_divide) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    long long arr[n][3];
    for(int i = 1;i<=n;i++){
        long long x,g,en;
        cin>>x>>g>>en;
        arr[i][0] = x, arr[i][1] = g,arr[i][2] = en;
    }
    vector<pair<long long,long long>> v;
    long long dist = 0 , energy = 0 , gold = 0;
    for(int i = 1;i<=n;i++){
        if(i>1)dist+=arr[i][0]-arr[i-1][0];
        v.push_back({energy-dist,gold});
        energy+=arr[i][2];
        gold+=arr[i][1];
    }
    long long tab[n];
    sort(v.begin(),v.end());
    long long mi = 1e18;
    for(int i = 0;i<n;i++){
        mi = min(mi,v[i].second);
        tab[i] = mi;
    }
    long long ma = 0;
    dist = 0 , energy = 0 , gold = 0;
    for(int i = 1;i<=n;i++){
        ma = max(ma,arr[i][1]);
        energy+=arr[i][2];
        gold+=arr[i][1];
        if(i>1)dist+=arr[i][0]-arr[i-1][0];
        if(energy-dist>=0){
            ma = max(ma,gold);
        }else{
            pair<long long,long long>p = {energy-dist+1,-1};
            int it = lower_bound(v.begin(),v.end(),p)-v.begin();
            it--;
            if(it>=0){
                ma = max(ma,gold-tab[it]);
            }
        }
    }
    cout<<ma;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -