Submission #1079657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079657		danikoynov	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	3 ms	860 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];

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

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]);
    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];
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, 1, n);
    for (pair < Fraction, pair < ll, ll > > event : events)
    {
        //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, 1, n, pivot);

        Node lf = query(1, 1, n, 1, pivot), rf = query(1, 1, 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: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20