제출 #1185861

#제출 시각아이디문제언어결과실행 시간메모리
1185861FaresSTH금 캐기 (IZhO14_divide)C++20
17 / 100
0 ms328 KiB
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    vector<array<int,3>>a(n);
    for(auto&i:a)cin>>i[0]>>i[1]>>i[2];
    sort(a.begin(),a.end());
    ll pg[n],pe[n];
    pg[0]=a[0][1];
    pe[0]=a[0][2];
    for(int i=1;i<n;i++){
        pg[i]=pg[i-1]+a[i][1];
        pe[i]=pe[i-1]+a[i][2];
    }
    int l[n],p=0;
    l[0]=0;

    for(int i=1;i<n;i++){
        while(p<i&&pe[i]-(p?pe[p-1]:0)<a[i][0]-a[p][0])p++;
        l[i]=p;
    }
    int r[n];
    r[n-1]=n-1;
    p=n-1;

    for(int i=n-2;i>=0;i--){
        while(p>i&&pe[p]-(i?pe[i-1]:0)<a[p][0]-a[i][0])p--;
        r[i]=p;
    }
    ll res=1;

    for(int i=0;i<n;i++){
        res=max({res,pg[i]-(l[i]?pg[l[i]-1]:0),pg[r[i]]-(i?pg[i-1]:0)});
    }
    cout<<res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...