PROG-T1139: Campus

#include <iostream>
#include <vector>
#include <tuple>
#include <math.h>
using namespace std;

#define lli long long
#define tiii tuple<int, int, int>

vector<tiii> dorm;
int nd;

lli SumDist(lli place, int mode){ /// 0 => Row 1 => Col
    lli sum = 0;
    for(auto d : dorm){
        int p = (mode == 0)? get<0>(d) : get<1>(d);
        int stu = get<2>(d);
        sum += (abs(p - place)) * stu;
    }
    return sum;
}

lli BSBuilding(int mn, int mx, int mode){ /// 0 => Row 1 => Col
    lli l = mn;
    lli r = mx - 1;
    lli ans = 1e18;
    while(l <= r){
        lli m = (l + r) / 2;
        lli s1 = SumDist(m, mode);
        lli s2 = SumDist(m + 1, mode);
        ans = min(ans, min(s1, s2));
        if(s1 > s2){
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans;
}

int main(){

    int r, c, stu, mxr, mnr, mxc, mnc;
    scanf("%d", &nd);

    mxr = 1;
    mnr = 1e9;
    mxc = 1;
    mnc = 1e9;
    for(int i = 0; i < nd; ++i){
        scanf("%d %d %d", &r, &c, &stu);
        dorm.emplace_back(r, c, stu);
        mxr = max(mxr, r);
        mnr = min(mnr, r);
        mxc = max(mxc, c);
        mnc = min(mnc, c);
    }

    cout << BSBuilding(mnr, mxr, 0) + BSBuilding(mnc, mxc, 1);

    return 0;
}