Submission #228148

#	Time	Username	Problem	Language	Result	Execution time	Memory
228148		qkxwsm	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2094 ms	145492 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, vi> > 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, vi> a, pair<pll, vi> 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.
    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});
            ve.PB({p, j});
        }
        sort(ALL(ve));
        // cerr << "ok\n";
        int iter = 0;
        pll dir; vi nodes; nodes.PB(i);
        FOR(j, 0, SZ(ve))
        {
            dir = ve[j].fi;
            // cerr << dir.fi << ' ' << dir.se << ' ' << ve[j].se << endl;
            nodes.PB(ve[j].se);
            if (j == N - 2 || ve[j + 1].fi != ve[j].fi)
            {
                events.PB({dir, nodes});
                for (int u : nodes)
                {
                    for (int v : nodes)
                    {
                        mark[u][v] = true;
                    }
                }
                nodes.clear();
                nodes.PB(i);
            }
        }
    }
    build(1, 0, N - 1);
    ckmax(ans, seg[1][0][0]);
    // cerr << "return " << seg[1][0][0] << endl;
    sort(ALL(events), cmp2);
    // cerr << "alive\n";
    FOR(i, 0, SZ(events))
    {
        auto a = events[i];
        // cerr << "size " << SZ(a.se) << endl;
        //reverse everything for a.
        int lt = a.se.front(), rt = a.se.back();
        // cerr << "swap " << lt << ' ' << rt << endl;
        int pl = pos[lt], pr = pos[rt];
        //reverse everything in (pl..pr)
        for (int x : a.se)
        {
            pos[x] = pl + pr - pos[x];
            update(1, 0, N - 1, pos[x], arr[x].w);
        }
        //you can take all of it.
        ckmax(ans, seg[1][0][0]);
        // cerr << "return " << seg[1][0][0] << endl;
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int32_t main()':
bulldozer.cpp:157:13: warning: unused variable 'iter' [-Wunused-variable]
         int iter = 0;
             ^~~~

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