Submission #1185315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185315		12345678	Bulldozer (JOI17_bulldozer)	C++20	0 / 100	40 ms	324 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=105;

struct fraction
{
    ll a, b, t, idx;
    fraction(ll a=0, ll b=0, ll t=0, ll idx=0): a(a), b(b), t(t), idx(idx) {}
    bool operator< (const fraction &o) const
    {
        if (a*o.b==b*o.a) return t<o.t;
        return a*o.b<b*o.a;
    }
};

ll n, x[nx], y[nx], v[nx], res;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i]>>v[i];
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (i==j) continue;
            vector<fraction> c;
            fraction m=fraction(y[j]-y[i], x[j]-x[i], 0, 0);
            for (int k=1; k<=n; k++)
            {
                if (k==j) c.push_back(fraction(y[k]*m.b-m.a*x[k], m.b, 1, k));
                else c.push_back(fraction(y[k]*m.b-m.a*x[k], m.b, 0, k));
            }
            sort(c.begin(), c.end());
            ll mn=0, sm=0;
            for (auto cur:c) sm+=v[cur.idx], res=max(res, sm-mn), mn=min(mn, sm);
        }
    }
    cout<<res;
}

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