제출 #1198875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198875		aguss	Bulldozer (JOI17_bulldozer)	C++20	5 / 100	61 ms	432 KiB

bulldozer

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ": " << x << "\n";
using namespace std;
double calc_dis(double x1, double x2, double y1, double y2, double x, double y){
    double num = abs((x2 - x1) * (y1 - y) - (x1 - x) * (y2 - y1));
    double den = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
    return num / den;
}

double sign(double x1, double x2, double y1, double y2, double x, double y){
    double cruz = (x2 - x1) * (y - y1) - (y2 - y1) * (x - x1); 
    if(cruz > 0) return -1;
    if(cruz < 0) return 1; 
    return 0;
}

void kadane(const vector<pair<double, long long>> &arr, long long &ans){
    long long aux = 0;
    for(int i = 0; i < (int)arr.size(); i++){
        aux = max(aux + arr[i].second, arr[i].second);
        ans = max(ans, aux); 
    } 
}

int main(){
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    vector<long long> v(n);
    long long ans = 0;
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> v[i];
    vector<pair<double, long long>> noche;
    map<long long, long long> otro;
    for(int i = 0; i < n; i++){
        otro[x[i]] += v[i];
    }
    for(const auto &[a, b] : otro){
        noche.push_back({a, b});
    }
    sort(noche.begin(), noche.end());
    kadane(noche, ans);
    //dbg(ans);
    string linea = "=============";
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(x[i] == x[j]) continue;
            //dbg(i);
            //dbg(j);
            vector<pair<double, long long>> aux;
            map<long long, long long> check;
            check[0] = v[i] + v[j];
            //dbg(v[i]);
            //dbg(v[j]);
            //dbg(check[0]);
            for(int k = 0; k < n; k++){
                if(k == i or k == j) continue;
                double sgn = sign(x[i], x[j], y[i], y[j], x[k], y[k]);
                double dis = calc_dis(x[i], x[j], y[i], y[j], x[k], y[k]);
                double ago = sgn * dis;
                long long key = round(ago * 1e6);
                //dbg(v[k]);
                check[key] += v[k];
            }
            for(const auto &[a, b] : check){
                aux.push_back({a, b});
            }
            sort(aux.begin(), aux.end());
            kadane(aux, ans); 
            //dbg(ans);
            //dbg(linea);
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20