Submission #361926

#	Time	Username	Problem	Language	Result	Execution time	Memory
361926		RyoPham	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	850 ms	33792 KiB

bulldozer

#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 2005;

struct segment_tree
{
    lli total[maxn * 4];
    lli max_pref[maxn * 4], max_suff[maxn * 4], max_sub[maxn * 4];

    void update(int x, int l, int r, int p, int k)
    {
        if(l == r)
        {
            total[x] = k;
            max_sub[x] = max_pref[x] = max_suff[x] = max(0, k);
            return;
        }
        int mid = (l + r) / 2;
        if(p <= mid) update(x * 2, l, mid, p, k);
        else update(x * 2 + 1, mid + 1, r, p, k);
        total[x] = total[x * 2] + total[x * 2 + 1];
        max_pref[x] = max(max_pref[x * 2], total[x * 2] + max_pref[x * 2 + 1]);
        max_suff[x] = max(max_suff[x * 2 + 1], total[x * 2 + 1] + max_suff[x * 2]);
        max_sub[x] = max(max(max_sub[x * 2], max_sub[x * 2 + 1]),
                         max_suff[x * 2] + max_pref[x * 2 + 1]);
    }

    lli get_max_sub()
    {
        return max_sub[1];
    }
} tree;

struct point
{
    int x, y;

    point() {}
    point(int _x, int _y) : x(_x), y(_y) {}

    bool operator <(const point&other) const
    {
        if(y == other.y) return x < other.x;
        return y > other.y;
    }
};

struct frac
{
    int a, b;

    frac() {}
    frac(int _a, int _b)
    {
        a = _a;
        b = _b;
    }

    bool operator <(const frac&other) const
    {
        return a * 1LL * other.b < b * 1LL * other.a;
    }

    bool operator ==(const frac&other) const
    {
        return a * 1LL * other.b == b * 1LL * other.a;
    }
};

int n;
pair<point, int> a[maxn];

int pos[maxn];
vector<pair<frac, pii>> events;

void read_input()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;
        a[i] = make_pair(point(x, y), w);
    }
}

void init()
{
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i)
    {
        tree.update(1, 1, n, i, a[i].se);
        pos[i] = i;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
            if(a[i].fi.y != a[j].fi.y)
            {
                int dx = a[j].fi.x - a[i].fi.x;
                int dy = a[i].fi.y - a[j].fi.y;
                events.push_back(make_pair(frac(dx, dy), pii(i, j)));
            }
    sort(events.begin(), events.end());
}

void solve()
{
    lli ans = tree.get_max_sub();
    for(int i = 0; i < sz(events); )
    {
        int j = i + 1;
        while(j < sz(events) && events[i].fi == events[j].fi)
            ++j;
        for(; i < j; ++i)
        {
            int p = events[i].se.fi, q = events[i].se.se;
            tree.update(1, 1, n, pos[p], a[q].se);
            tree.update(1, 1, n, pos[q], a[p].se);
            swap(pos[p], pos[q]);
        }
        ans = max(ans, tree.get_max_sub());
    }
    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    init();
    solve();
}

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