Submission #1359926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359926		hashimzaderashid	Monsters (NOI25_monsters)	C++20	100 / 100	157 ms	6652 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ll t,a,b,c,d,e,f,g;
    cin>>a>>b;
    vector<pair<ll,ll>>vp;
    for(int i = 0;i<a;i++){
        cin>>c>>d;
        vp.push_back({c,d});
    }
    vector<ll>v(b);
    for(int i = 0;i<b;i++){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    sort(vp.begin(),vp.end());
    vector<ll>ch(b,0);
    ll ans = 0;
    for(int i = 0;i<a;i++){
        auto it = lower_bound(v.begin(),v.end(),vp[i].first);
        auto it2 = it;
        if(it == v.begin()){
            ll idx = it-v.begin();
            if(*it-vp[i].first < vp[i].second){
                ch[idx] = 1;
                ans += *it-vp[i].first;
            }
            else{
                ans += vp[i].second;
            }
        }
        else if(it == v.end()){
            it2--;
            ll idx = it2-v.begin();
            if(vp[i].first-*it2 < vp[i].second){
                ch[idx] = 1;
                ans += vp[i].first-*it2;
            }
            else{
                ans += vp[i].second;
            }
        }
        else{
            it2--;
            ll idx = it-v.begin();
            ll idx2 = it2-v.begin();
            if(min(*it-vp[i].first,vp[i].first-*it2) < vp[i].second){
                if(*it-vp[i].first == vp[i].first-*it2){
                    if(ch[idx2]){
                        ch[idx2]++;
                        ans += vp[i].first-*it2;
                    }
                    else{
                        ch[idx]++;
                        ans += *it-vp[i].first;
                    }
                }
                else if(*it-vp[i].first < vp[i].first-*it2){
                    ch[idx]++;
                    ans += *it-vp[i].first;
                }
                else{
                    ch[idx2]++;
                    ans += vp[i].first-*it2;
                }
            }
            else{
                ans += vp[i].second;
            }
        }
    }
    ll cnt = 0;
    for(int i = 0;i<b;i++){
        if(ch[i]){
            cnt++;
        }
    }
    ans += cnt;
    cout<<ans<<endl;
}
//By Rashid_Hashimzade

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 30 / 30
• Subtask 5: 29 / 29
• Subtask 6: 11 / 11