IPST59: Signal Strength

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 150 + 5;
const int NN = 150 * 150 + 5;

vector<pii> sortedDist, cnt(1);
vector<int> dist(1);
pii coor[N];
int dp[2][NN];

int distance(int u, int v){
    int dx = coor[u].first - coor[v].first;
    int dy = coor[u].second - coor[v].second;
    return dx * dx + dy * dy;
}

int main(){

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d", &coor[i].first, &coor[i].second);
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            int access;
            scanf("%d", &access);
            sortedDist.emplace_back(distance(i, j), access);
        }
    }
    sort(sortedDist.begin(), sortedDist.end());
    int lst = -1;
    for(pii p : sortedDist){
        int d = p.first;
        int acc = p.second;
        if(d != lst){
            dist.push_back(d);
            cnt.emplace_back(0, 0);
            lst = d;
        }
        if(acc == 1){
            ++cnt.back().first;
        } else {
            ++cnt.back().second;
        }
    }
    n = (int)dist.size() - 1;
    for(int i = n; i >= 1; --i){
        dp[0][i] = cnt[i].first + dp[0][i + 1];
        dp[1][i] = min(cnt[i].second + dp[1][i + 1], dp[0][i]);
    }
    cout << dp[1][1];

    return 0;
}