제출 #1359926

#제출 시각아이디문제언어결과실행 시간메모리
1359926hashimzaderashidMonsters (NOI25_monsters)C++20
100 / 100
157 ms6652 KiB
#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
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…