Submission #228158

#	Time	Username	Problem	Language	Result	Execution time	Memory
228158		qkxwsm	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	7 ms	896 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef array<array<ll, 2>, 2> dparr;

const int MAXN = 2053;

struct point
{
    int x, y, w;
};

int N;
point arr[MAXN];
bool mark[MAXN][MAXN];
vector<pair<pll, pii> > events;
dparr seg[2 * MAXN];
int pos[MAXN];
ll ans;

dparr comb(dparr lt, dparr rt)
{
    dparr res;
    res[0][0] = max(lt[0][1] + rt[1][0], max(lt[0][0], rt[0][0]));
    res[0][1] = max(lt[0][1] + rt[1][1], rt[0][1]);
    res[1][0] = max(lt[1][0], lt[1][1] + rt[1][0]);
    res[1][1] = lt[1][1] + rt[1][1];
    return res;
}
void build(int w, int L, int R)
{
    if (L == R)
    {
        FOR(i, 0, 2) FOR(j, 0, 2) seg[w][i][j] = arr[L].w;
        return;
    }
    int mid = (L + R) >> 1;
    build(w << 1, L, mid);
    build(w << 1 | 1, mid + 1, R);
    seg[w] = comb(seg[w << 1], seg[w << 1 | 1]);
}
void update(int w, int L, int R, int a, int v)
{
    if (L == R)
    {
        FOR(i, 0, 2) FOR(j, 0, 2) seg[w][i][j] = v;
        return;
    }
    int mid = (L + R) >> 1;
    if (a <= mid) update(w << 1, L, mid, a, v);
    else update(w << 1 | 1, mid + 1, R, a, v);
    seg[w] = comb(seg[w << 1], seg[w << 1 | 1]);
}

ll gcd(ll a, ll b)
{
    return (b == 0 ? a : gcd(b, a % b));
}
pll normalize(pll p)
{
    ll g = gcd(abs(p.fi), abs(p.se));
    p.fi /= g; p.se /= g;
    if (p.se < 0)
    {
        p.se = -p.se;
        p.fi = -p.fi;
    }
    if (p.se == 0 && p.fi < 0)
    {
        p.fi = -p.fi;
    }
    return p;
}
bool cmp1(point a, point b)
{
    if (a.y != b.y)
    {
        return a.y < b.y;
    }
    return a.x < b.x;
}
bool cmp(pll a, pll b)
{
    return a.fi * b.se > b.fi * a.se;
}
bool cmp2(pair<pll, pii> a, pair<pll, pii> b)
{
    return cmp(a.fi, b.fi);
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    FOR(i, 0, N)
    {
        cin >> arr[i].x >> arr[i].y >> arr[i].w;
        ckmax(ans, arr[i].w);
    }
    sort(arr, arr + N, cmp1);
    iota(pos, pos + N, 0);
    build(1, 0, N - 1);
    // FOR(i, 0, N)
    // {
    //     cerr << arr[i].x << ' ' << arr[i].y << ' ' << arr[i].w << endl;
    // }
    //consider the order of the points. rotate the line sideways.
    //then, at a given slope, some vectors of lines reverse order.
    events.reserve(N * (N - 1) / 2);
    FOR(i, 0, N)
    {
        vector<pair<pll, int> > ve;
        FOR(j, i + 1, N)
        {
            if (mark[i][j])
            {
                continue;
            }
            pll p = normalize({arr[j].x - arr[i].x, arr[j].y - arr[i].y});
            events.PB({p, {i, j}});
        }
    }
    build(1, 0, N - 1);
    sort(ALL(events), cmp2);
    cout << ans << '\n';
    // cerr << "alive\n";
    FOR(i, 0, SZ(events))
    {
        auto a = events[i];
        pii p = a.se;
        swap(pos[p.fi], pos[p.se]);
        // cerr << "it swaps " << p.fi << ' ' << p.se << endl;
        update(1, 0, N - 1, pos[p.fi], arr[p.fi].w);
        update(1, 0, N - 1, pos[p.se], arr[p.se].w);
        //you can take all of it.
        if (i == SZ(events) - 1 || events[i].fi != events[i + 1].fi)
        {
            assert(i == SZ(events) - 1);
            ckmax(ans, seg[1][0][0]);
        }
        // cerr << "return " << seg[1][0][0] << endl;
    }
    // cout << ans << '\n';
    return 0;
}

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