Submission #887667

#	Time	Username	Problem	Language	Result	Execution time	Memory
887667		Maite_Morale	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	401 ms	44456 KiB

Main

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll pass[MAX],n;
pll a[MAX];
int main(){
    fast_in
    cin>>n;priority_queue<pair<pll,ll>> q;
    for(int i=0;i<n;i++){
        cin>>a[i].F>>a[i].S;
    }sort(a,a+n);
    for(int i=0;i<n;i++)
        q.push({{a[i].S,(ll)-1},i});
    ll r=0;
    while(!q.empty()){
         pair<pll,ll> u=q.top();q.pop();
         //cout<<u.S<<" "<<u.F.F<<"\n";
         if(pass[u.S]==1)continue;
         pass[u.S]=1;r-=u.F.S;
        if(u.S>0)   q.push({{u.F.F-abs(a[u.S].F-a[u.S-1].F),(ll)0},u.S-1});
        if(u.S<n-1) q.push({{u.F.F-abs(a[u.S].F-a[u.S+1].F),(ll)0},u.S+1});
    }
    cout<<r;
return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31