제출 #1039074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039074		biserailieva	Art Exhibition (JOI18_art)	C++14	100 / 100	718 ms	87428 KiB

art

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAXN 500001
 
long long n;
vector<pair<long long,long long>> vec;
long long pref[MAXN];
map<long long,long long> pos;
map<long long,long long> prv;
 
int main()
{
    cin>>n;
    vec.push_back({0,0});
    for (long long i=1;i<=n;i++)
    {
        long long a,b;cin>>a>>b;
        vec.push_back({a,b});
    }
    sort(vec.begin(),vec.end());
    pref[0]=0;
    for (long long i=1;i<=n;i++) pref[i]=pref[i-1]+vec[i].second;
    for (long long i=1;i<=n;i++)
    {
        pos[vec[i].first]=i;
        if (prv.find(vec[i].first)==prv.end()) prv[vec[i].first]=i;
    }
    long long ans=pref[pos[vec[1].first]];
    long long trenmaks=vec[1].first;
    for (auto&p:pos)
    {
        if (p.first==vec[1].first) continue;
        long long desno=p.second,a3=p.first;
        long long levo=prv[a3];
        long long s=pref[desno]-pref[levo-1];
        ans=max(ans,s);
        long long i=levo-1;
        long long val=s-a3+pref[i]+trenmaks;
        ans=max(ans,val);
        trenmaks=max(trenmaks,a3-pref[i]);
    }
    cout<<ans<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50