제출 #1350418

#제출 시각아이디문제언어결과실행 시간메모리
1350418bbbirosArt Exhibition (JOI18_art)C++20
0 / 100
0 ms344 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#define ll unsigned long long
#define X first
#define Y second
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
int n;
const int MAXN = 500100;
pair<ll, ll> a[MAXN];
vector<pair<ll,ll>> b;
ll mx = 0;

void read()
{
    mx=0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].X >> a[i].Y;
        mx = max(mx, a[i].Y);
    }
    sort(a + 1, a + 1 + n);
    for(int i=1;i<=n;i++)
    {
        if(b.empty())
        {
            b.push_back(a[i]);
            continue;
        }
        if(b.back().X==a[i].X)b.back().Y+=a[i].Y;
        else b.push_back(a[i]);
    }
}
void solve()
{
    int l = 0;
    ll sum = 0;
    for (int r = 0; r < b.size(); r++)
    {
        sum+=a[r].Y;
        while(l<r&&((a[l+1].X-a[l].X)>a[l].Y))
        {
            sum-=a[l].Y;
            l++;
        }
        mx=max(mx,sum-(a[r].X-a[l].X));
    }
}
signed main()
{
    speed();
    read();
    solve();
    cout<<mx<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...