oj.uz

Submission #550538

# Submission time Handle Problem Language Result Execution time Memory
550538 2022-04-18T11:12:27 Z Kipras Art Exhibition (JOI18_art) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll maxN = 5e5+10;

vector<pair<ll, ll>> a;
map<ll, ll> b;
ll n;

int main()
{

    ios_base::sync_with_stdio(0);cin.tie(nullptr);

    cin>>n;

    for(int i = 0; i < n; i++){
        ll aa, bb;
        cin>>aa>>bb;
        a.push_back({aa, bb});
    }


    for(int i = 0; i < n; i++){
        b[a[i].first]+=a[i].second;
    }

    a.clear();

    for(auto i : b){
        a.push_back({i.first, i.second});
    }

    sort(a.begin(), a.end());

    n = a.size();

    ll i = 0, j = 0;

    ll s=a[0].second;
    ll mx=0;

    while(j<n-1){
        //cout<<s<<" "<<i<<" "<<j<<" "<<abs(a[j].first-a[i].first)<<endl;
        mx=max(mx, s-abs(a[j].first-a[i].first));
        if(i!=j&&a[i+1].first-a[i].first>=a[i].second){
            s-=a[i].second;
            i++;
            continue;
        }
        j++;
        s+=a[j].second;
    }
    while(i<n){
        mx=max(mx, s-abs(a[j].first-a[i].first));
        s-=a[i].second;
        i++;
    }
    mx=max(mx, s-abs(a[j].first-a[i].first));

    cout<<mx;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -