Submission #1350431

#TimeUsernameProblemLanguageResultExecution timeMemory
1350431bbbirosArt Exhibition (JOI18_art)C++20
50 / 100
1096 ms24084 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#define ll 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;
vector<ll> pref;
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);
    b.push_back({0, 0});
    for (int i = 1; i <= n; i++)
    {
        if (b.back().X == a[i].X)
            b.back().Y += a[i].Y;
        else
            b.push_back(a[i]);
    }
    pref.push_back(0);
    for (int i = 1; i < b.size(); i++)
    {
        //cout << b[i].X << ' ' << b[i].Y << endl;
        pref.push_back( pref[i - 1] + b[i].Y);
    }
}
void solve()
{
    for (int l = 1; l < b.size(); l++)
        for (int r = l; r < b.size(); r++)
        {
            mx = max(mx, (pref[r] - pref[l - 1]) - (b[r].X - b[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...