Submission #1079663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079663		danikoynov	Bulldozer (JOI17_bulldozer)	C++14	80 / 100	1591 ms	65436 KiB

bulldozer

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

struct Point
{
    ll x, y;
    
    Point(ll _x = 0, ll _y = 0)
    {
        x = _x;
        y = _y;
    }
    
    void input()
    {
        cin >> x >> y;
    }
};
    
const int MAXN = 2010;
int n;
pair < Point, ll > spot[MAXN];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        spot[i].first.input();
        cin >> spot[i].second;
    }
}

struct Fraction
{
    ll num, dev;

    Fraction(ll _num = 0, ll _dev = 0)
    {
        num = _num;
        dev = _dev;
    }

    void rationalize()
    {
        ll nod = __gcd(num, dev);
        if (nod < 0)
            nod = - nod;
        num /= nod;
        dev /= nod;
    }

    bool operator < (const Fraction f) const
    {
        /// num / dev < f.num / f.dev
        return (num * f.dev) < (f.num * dev);
    }
};


bool cmp(pair < Point, ll > p1, pair < Point, ll > p2)
{
    if (p1.first.x != p2.first.x)
        return p1.first.x < p2.first.x;
    return p1.first.y > p2.first.y;
}


const ll INF = 1e18;

struct Node
{
    ll val[2], res;

    Node()
    {
        val[0] = INF;
        val[1] = -INF;
        res = 0;
    }
};

Node unite(Node lf, Node rf)
{
    Node mf;
    mf.val[0] = min(lf.val[0], rf.val[0]);
    mf.val[1] = max(lf.val[1], rf.val[1]);
    mf.res = max(lf.res, rf.res);
    mf.res = max(mf.res, rf.val[1] - lf.val[0]);
    return mf;
}

Node tree[4 * MAXN];
ll pref[MAXN];

void build(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].val[0] = tree[root].val[1] = pref[left];
        return;
    }

    int mid = (left + right) / 2;
    build(root * 2, left, mid);
    build(root * 2 + 1, mid + 1, right);

    tree[root] = unite(tree[root * 2], tree[root * 2 + 1]);
}

void update(int root, int left, int right, int pivot)
{
    if (left == right)
    {
        tree[root].val[0] = tree[root].val[1] = pref[left];
        return;
    }

    int mid = (left + right) / 2;
    if (pivot <= mid)
        update(root * 2, left, mid, pivot);
    else
        update(root * 2 + 1, mid + 1, right, pivot);
    
    tree[root] = unite(tree[root * 2], tree[root * 2 + 1]);
}

Node query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return Node();

    if (left >= qleft && right <= qright)
        return tree[root];
    
    int mid = (left + right) / 2;
    return unite(query(root * 2, left, mid, qleft, qright),
            query(root * 2 + 1, mid + 1, right, qleft, qright));
}


int position[MAXN], swapped[MAXN][MAXN];

Fraction get_slope(Point p1, Point p2)
{
    if (p1.x > p2.x)
        swap(p1, p2);
    Fraction slope(p2.y - p1.y, p2.x - p1.x);
    slope.rationalize();
    return slope;
}

void simulate()
{
    if (n == 1)
    {
        ll result = 0;
        result = max(result, spot[1].second);
        cout << result << endl;
        return;
    }

    sort(spot + 1, spot + n + 1, cmp);
    for (int i = 1; i <= n; i ++)
        position[i] = i;

    vector < pair < Fraction, pair < int, int > > > events;
    for (int i = 1; i <= n; i ++)
        for (int j = i + 1; j <= n; j ++)
        {
            Fraction slope(spot[j].first.y - spot[i].first.y, 
                    spot[j].first.x - spot[i].first.x);
            slope.rationalize();
            events.push_back({slope, {i, j}});
        }

    sort(events.begin(), events.end());

    ll sum = 0, result = 0;
    for (int i = 1; i <= n; i ++)
    {
        sum += spot[i].second;
        if (sum < 0)
            sum = 0;
        result = max(result, sum);
        pref[i] = pref[i - 1] + spot[i].second;
    }
    //cout << "begin " << tree[1].best_sum << " " << cur << endl;
    
    build(1, 0, n);

    set < pair < Fraction, int > > change;
    for (int i = 1; i < n; i ++)
    {
        Fraction slope(spot[i + 1].first.y - spot[i].first.y, 
                spot[i + 1].first.x - spot[i].first.x);
        slope.rationalize();
        change.insert({slope, i});
    }

    ///for (pair < Fraction, pair < ll, ll > > event : events)
    while(!change.empty())
    {
        Fraction cur = (*change.begin()).first;
        //cout << "----------------" << endl;
        while(!change.empty())
        {
            if (cur < (*change.begin()).first)
                break;
            int pivot = (*change.begin()).second;
            //cout << "points: " << endl;
            //for (int i = 1; i <= n; i ++)
            //{
            //    cout << spot[i].first.x << " : " << spot[i].first.y << endl;
            //}
            //cout << "pivot " << pivot << " " << (*change.begin()).first.num << " / " << (*change.begin()).first.dev << endl;
            //cout << "swap " << postion[pivot] << " : " << postion
            change.erase(change.begin());
            if (pivot > 1 && !swapped[position[pivot - 1]][position[pivot]])
                change.erase({get_slope(spot[pivot].first, spot[pivot - 1].first), pivot - 1});
            if (pivot + 2 <= n && !swapped[position[pivot + 1]][position[pivot + 2]])
                change.erase({get_slope(spot[pivot + 2].first, spot[pivot + 1].first), pivot + 1});
            
            pref[pivot] -= spot[pivot].second;
            pref[pivot] += spot[pivot + 1].second;

            update(1, 0, n, pivot);

            /**Node lf = query(1, 0, n, 0, pivot), rf = query(1, 0, n, pivot, n);
            result = max(result, pref[pivot] - lf.val[0]);
            result = max(result, rf.val[1] - pref[pivot]);*/
            
            swapped[position[pivot]][position[pivot + 1]] = 1;
            swapped[position[pivot + 1]][position[pivot]] = 1;
            swap(position[pivot], position[pivot + 1]);
            swap(spot[pivot], spot[pivot + 1]);

            if (pivot > 1 && !swapped[position[pivot - 1]][position[pivot]])
                change.insert({get_slope(spot[pivot].first, spot[pivot - 1].first), pivot - 1});
            if (pivot + 2 <= n && !swapped[position[pivot + 1]][position[pivot + 2]])
                change.insert({get_slope(spot[pivot + 2].first, spot[pivot + 1].first), pivot + 1});

        }

        result = max(result, tree[1].res);
        /**sum = 0;
        for (int i = 1; i <= n; i ++)
        {
            sum += spot[i].second;
            if (sum < 0)
                sum = 0;
            result = max(result, sum);
        }*/
        //Fraction slope = event.first;
        /**pair < ll, ll > pivots = event.second;
        //cout << pivots.first << " : " << pivots.second << endl;
        assert(abs(position[pivots.first] - position[pivots.second]) == 1);
        int pivot = min(position[pivots.first], position[pivots.second]);
        pref[pivot] -= spot[pivot].second;
        pref[pivot] += spot[pivot + 1].second;
        swap(spot[position[pivots.first]], spot[position[pivots.second]]);
        swap(position[pivots.first], position[pivots.second]);
        update(1, 0, n, pivot);

        Node lf = query(1, 0, n, 0, pivot), rf = query(1, 0, n, pivot, n);
        result = max(result, pref[pivot] - lf.val[0]);
        result = max(result, rf.val[1] - pref[pivot]);*/
        /**
        sum = 0, cur = 0;;
        for (int i = 1; i <= n; i ++)
        {
            sum += spot[i].second;
            if (sum < 0)
                sum = 0;
            cur = max(cur, sum);
            //result = max(result, sum);
        }

        cout << "step " << tree[1].best_sum << " " << cur << endl;*/
    }

    cout << result << endl;
}

void solve()
{
    input();
    simulate();
}
int main()
{   
    solve();
    return 0;
}

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