Submission #44588

#	Time	Username	Problem	Language	Result	Execution time	Memory
44588		choikiwon	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1393 ms	33484 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;

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

ll cross(pii a, pii b) {
    return 1LL * a.first * b.second - 1LL * a.second * b.first;
}

int N;
struct Point {
    int x, y, w;
    bool operator <(const Point &i) const {
        return y < i.y || (y == i.y && x < i.x);
    }
};
Point P[2010];
int pnt[2010];
vector<pair<pii, pii> > line;
ll ans;

bool cmp(pair<pii, pii> a, pair<pii, pii> b) {
    if(cross(a.first, b.first) != 0) return cross(a.first, b.first) > 0;
    return a.second < b.second;
}

struct node {
    int len;
    ll sum, mx, lmx, rmx;
};

node mrg(node &a, node &b) {
    node ret;
    ret.len = a.len + b.len;
    ret.sum = a.sum + b.sum;
    ret.lmx = max(a.lmx, a.sum + b.lmx);
    ret.rmx = max(b.rmx, b.sum + a.rmx);
    ret.mx = max(a.mx, b.mx);
    ret.mx = max(ret.mx, a.rmx + b.lmx);
    return ret;
}

struct BIT {
    vector<node> tree;
    void init() {
        tree = vector<node>(4 * N);
        build(0, N - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = { 1, P[l].w, P[l].w, P[l].w, P[l].w };
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = mrg(tree[2*n], tree[2*n + 1]);
    }
    void upd(int idx, node val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = val;
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = mrg(tree[2*n], tree[2*n + 1]);
    }
} bit;

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d %d %d", &P[i].x, &P[i].y, &P[i].w);
    }

    sort(P, P + N);

    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
            line.push_back({ { P[j].x - P[i].x, P[j].y - P[i].y }, {i, j} });
        }
    }
    for(int i = 0; i < N; i++) pnt[i] = i;

    sort(line.begin(), line.end(), cmp);

    bit.init();
    ans = max(ans, bit.tree[1].mx);

    int s = 0;
    for(int i = 0; i < line.size(); i++) {
        if(i == (int)line.size() - 1 || cross(line[i].first, line[i + 1].first) != 0) {
            for(int j = s; j <= i; j++) {
                int a = line[j].second.first;
                int b = line[j].second.second;
                swap(P[ pnt[a] ], P[ pnt[b] ]);
                swap(pnt[a], pnt[b]);

                bit.upd(pnt[a], { 1, P[ pnt[a] ].w, P[ pnt[a] ].w, P[ pnt[a] ].w, P[ pnt[a] ].w }, 0, N - 1, 1);
                bit.upd(pnt[b], { 1, P[ pnt[b] ].w, P[ pnt[b] ].w, P[ pnt[b] ].w, P[ pnt[b] ].w }, 0, N - 1, 1);
            }

            ans = max(ans, bit.tree[1].mx);
            s = i + 1;
        }
    }

    printf("%lld", ans);
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < line.size(); i++) {
                    ~~^~~~~~~~~~~~~
bulldozer.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
bulldozer.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &P[i].x, &P[i].y, &P[i].w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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