Submission #1198887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198887		simplemind_31	Bulldozer (JOI17_bulldozer)	C++20	0 / 100	272 ms	452 KiB

bulldozer

#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
ll n,maxi;
bool cmp(vector<ll> a,vector<ll> b){
    if(a[1]<0) {
        a[0]=-a[0];
        a[1]=-a[1];
    }
    if(b[1]<0) {
        b[0]=-b[0];
        b[1]=-b[1];
    }
    return a[0]*b[1]<a[1]*b[0];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    vector<vector<ll>> points(n,{0,0,0});
    for(ll i=0;i<n;i++){
        cin >> points[i][0] >> points[i][1] >> points[i][2];
    }
    for(ll i=0;i<n;i++){
        for(ll j=i+1;j<n;j++){
            pair<ll,ll> pendiente={points[j][1]-points[i][1],points[j][0]-points[i][0]};
            if(pendiente.first==0){
                //vertical
                vector<pair<ll,ll>> nums(n);
                for(int k=0;k<n;k++){
                    nums[k]={points[k][1],points[k][2]};
                }
                sort(ALL(nums));
                ll sum=0;
                for(int k=0;k<n;k++){
                    maxi=max(maxi,sum=max(nums[k].second,sum+nums[k].second));
                }
            }else{
                //pair<ll,ll> perpendicular={-pendiente.second,pendiente.first};
                vector<vector<ll>> nums(n);
                ll ab=pendiente.first*pendiente.first+pendiente.second*pendiente.second;
                for(ll k=0;k<n;k++){
                    nums[k]={pendiente.first*(pendiente.first*points[k][0]-pendiente.second*points[k][1]),ab,points[k][2]};
                }
                sort(ALL(nums),cmp);
                ll sum=0;
                for(int k=0;k<n;k++){
                    maxi=max(maxi,sum=max(nums[k][2],sum+nums[k][2]));
                }
            }
            swap(points[i],points[j]);
            if(pendiente.first==0){
                //vertical
                vector<pair<ll,ll>> nums(n);
                for(int k=0;k<n;k++){
                    nums[k]={points[k][1],points[k][2]};
                }
                sort(ALL(nums));
                ll sum=0;
                for(int k=0;k<n;k++){
                    maxi=max(maxi,sum=max(nums[k].second,sum+nums[k].second));
                }
            }else{
                //pair<ll,ll> perpendicular={-pendiente.second,pendiente.first};
                vector<vector<ll>> nums(n);
                ll ab=pendiente.first*pendiente.first+pendiente.second*pendiente.second;
                for(ll k=0;k<n;k++){
                    nums[k]={pendiente.first*(pendiente.first*points[k][0]-pendiente.second*points[k][1]),ab,points[k][2]};
                }
                sort(ALL(nums),cmp);
                ll sum=0;
                for(int k=0;k<n;k++){
                    maxi=max(maxi,sum=max(nums[k][2],sum+nums[k][2]));
                }
            }
            swap(points[i],points[j]);
        }
    }
    cout << maxi;
}

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