Submission #1154529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154529		Otalp	Bulldozer (JOI17_bulldozer)	C++20	0 / 100	18 ms	324 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map
#define all(x) (x).begin(), (x).end()

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int MAXA = 2e5 + 5;

pair<pii, int> a[200100];

void solve(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i].ff.ff>>a[i].ff.ss;
        cin>>a[i].ss;
    }
    ll ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=i + 1; j<=n; j++){
            ll sum = 0;
            ll x1 = a[i].ff.ff, y1 = a[i].ff.ss;
            ll x2 = a[j].ff.ff, y2 = a[j].ff.ss;
            vector<pair<ll, ll> > d, q;
            for(int i=1; i<=n; i++){
                ll h = (y2-y1)*a[i].ff.ff-(x2-x1)*a[i].ff.ss+x2*y1-y2*x1;
                if(h >= 0) d.pb({h, a[i].ss});
                if(h <= 0) q.pb({-h, a[i].ss});
            }
            sort(all(d));
            sort(all(q));
            sum = 0;
            for(int i=0; i<d.size(); i++){
                sum += d[i].ss;
                if(i == d.size() - 1 or d[i + 1].ff != d[i].ff) ans = max(ans, sum);
            }
            sum = 0;
            for(int i=0; i<q.size(); i++){
                sum += q[i].ss;
                if(i == q.size() - 1 or q[i + 1].ff != q[i].ff) ans = max(ans, sum);
            }
        }
    }
    cout<<ans;  
}

int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<'\n';
    }
}

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