제출 #1356797

#제출 시각아이디문제언어결과실행 시간메모리
1356797nathlol2Monsters (NOI25_monsters)C++20
100 / 100
137 ms23956 KiB
#include <bits/stdc++.h>
#define int long long
#define fi first
#define sc second
using namespace std;
const int N = 2e5 + 5, INF = 2e9;
int n, k, ans, x[N];
pair<int, int> a[N];
set<int> s;
unordered_map<int, int> v;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for(int i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    for(int i = 1;i<=k;i++) cin >> x[i], s.insert(x[i]);
    sort(a + 1, a + n + 1);
    for(int i = 1;i<=n;i++){
        auto it = s.lower_bound(a[i].fi);
        int l = -INF, r = INF;
        if(it != s.end()) r = *it;
        if(it != s.begin()){
            --it;
            l = *it;
        }
        if(min(r - a[i].fi, a[i].fi - l) >= a[i].sc) ans += a[i].sc;
        else{
            ans += min(r - a[i].fi, a[i].fi - l);
            if(r - a[i].fi == a[i].fi - l){
                if(!v[l] && !v[r]){
                    v[r] = 1;
                    ++ans;
                }
            }else if(a[i].fi - l < r - a[i].fi){
                if(!v[l]) v[l] = 1, ++ans;
            }else{
                if(!v[r]) v[r] = 1, ++ans;
            }
        }
    }
    cout << ans;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…