Submission #1359422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359422		hashimzaderashid	Monsters (NOI25_monsters)	C++20	14 / 100	156 ms	9724 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<pair<ll,ll>>dis(a,{1e9,-1});
    for(int i = 0;i<a;i++){
        auto it = lower_bound(v.begin(),v.end(),vp[i].first);
        if(it != v.end()){
            if(*it-vp[i].first < dis[i].first){
                dis[i].first = *it-vp[i].first;
                ll idx = it-v.begin();
                dis[i].second = idx;
            }
        }
        if(it != v.begin()){
            it--;
            if(vp[i].first-*it < dis[i].first){
                dis[i].first = vp[i].first-*it;
                ll idx = it-v.begin();
                dis[i].second = idx;
            }
        }
    }
    ll ans = 0;
    vector<ll>ch(b,0);
    for(int i = 0;i<a;i++){
        if(dis[i].first < vp[i].second){
            ans += dis[i].first;
            ch[dis[i].second] = 1;
        }
        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: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 30
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11