Submission #540730

#	Time	Username	Problem	Language	Result	Execution time	Memory
540730		MrKustic	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2075 ms	133552 KiB

bulldozer

#include <iostream>
#include <algorithm>
#include <vector>
 
const int maxN = 2e3;
 
struct Point {
    int x, y, w;
    Point(int x = 0, int y = 0, int w = 0) : x(x), y(y), w(w) {}
    friend std::istream& operator>>(std::istream& is, Point& p) {
        is >> p.x >> p.y >> p.w;
        return is;
    }
} p[maxN];
 
struct Vector {
    int x, y;
    Vector(int x = 0, int y = 0) : x(x), y(y) {}
    Vector(const Point& p1, const Point& p2) : x(p2.x - p1.x), y(p2.y - p1.y) {}
    void normalize() {
        if (y < 0 || (y == 0 && x < 0)) {
            x = -x;
            y = -y;
        }
    }
};
 
struct Query {
    Vector v;
    std::vector<int> id;
} q[maxN * maxN / 2];
 
struct Item {
    long long min, max;
} t[4 * maxN + 4];
 
int n, it, a[maxN], b[maxN], c[maxN * maxN / 2];
long long pr[maxN + 1], ans, s;
std::pair<Vector, int> v[maxN];
std::vector<std::pair<int, int>> que;
 
long long crossp(const Vector& v1, const Vector& v2) {
    return 1LL * v1.x * v2.y - 1LL * v1.y * v2.x;
}
 
bool cmp(const std::pair<Vector, int>& a, const std::pair<Vector, int>& b) {
    return crossp(a.first, b.first) > 0;
}
 
bool cmp1(int i, int j) {
    return crossp(q[i].v, q[j].v) > 0;
}
 
bool cmp2(int i, int j) {
    Vector v0 = q[c[0]].v, v1 = Vector(p[q[c[0]].id[0]], p[i]), v2 = Vector(p[q[c[0]].id[0]], p[j]);
    long long c1 = crossp(v0, v1), c2 = crossp(v0, v2);
    if (c1 != c2)
        return c1 < c2;
    std::swap(v0.x, v0.y);
    v0.x = -v0.x;
    return crossp(v0, v1) > crossp(v0, v2);
}
 
void build(int i, int tl, int tr) {
    if (tr - tl == 1) {
        t[i].min = t[i].max = pr[tl];
        return;
    }
    int tm = (tl + tr) / 2;
    build(2 * i + 1, tl, tm);
    build(2 * i + 2, tm, tr);
    t[i].min = std::min(t[2 * i + 1].min, t[2 * i + 2].min);
    t[i].max = std::max(t[2 * i + 1].max, t[2 * i + 2].max);
}
 
void update(int i, int tl, int tr, int id) {
    if (tr - tl == 1) {
        t[i].min = t[i].max = pr[id];
        return;
    }
    int tm = (tl + tr) / 2;
    if (id < tm)
        update(2 * i + 1, tl, tm, id);
    else
        update(2 * i + 2, tm, tr, id);
    t[i].min = std::min(t[2 * i + 1].min, t[2 * i + 2].min);
    t[i].max = std::max(t[2 * i + 1].max, t[2 * i + 2].max);
}
 
long long getmin(int i, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r)
        return t[i].min;
    if (r <= tl || tr <= l)
        return 1e18;
    int tm = (tl + tr) / 2;
    return std::min(getmin(2 * i + 1, tl, tm, l, r), getmin(2 * i + 2, tm, tr, l, r));
}
 
long long getmax(int i, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r)
        return t[i].max;
    if (r <= tl || tr <= l)
        return -1e18;
    int tm = (tl + tr) / 2;
    return std::max(getmax(2 * i + 1, tl, tm, l, r), getmax(2 * i + 2, tm, tr, l, r));
}
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> p[i];
        a[i] = i;
    }
    if (n == 1) {
        std::cout << std::max(0, p[0].w);
        return 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            v[j] = { Vector(p[i], p[j]), j };
            v[j].first.normalize();
        }
        v[i] = v[n - 1];
        std::sort(v, v + n - 1, cmp);
        for (int l = 0, r = 0, id = i; l < n - 1; l = r, id = i) {
            while (r < n - 1 && crossp(v[l].first, v[r].first) == 0) {
                id = std::min(id, v[r].second);
                r++;
            }
            if (id == i) {
                q[it].v = v[l].first;
                q[it].id.push_back(i);
                for (int j = l; j < r; j++)
                    q[it].id.push_back(v[j].second);
                c[it] = it;
                it++;
            }
        }
    }
    std::sort(c, c + it, cmp1);
    std::sort(a, a + n, cmp2);
    for (int i = 0; i < n; i++) {
        b[a[i]] = i;
        pr[i + 1] = pr[i] + p[a[i]].w;
        ans = std::max(ans, pr[i + 1] - s);
        s = std::min(s, pr[i + 1]);
    }
    build(0, 0, n + 1);
    for (int i = 0; i < it; i++) {
        int id = c[i], l = n, r = 0;
        for (int j : q[id].id) {
            l = std::min(l, b[j]);
            r = std::max(r, b[j]);
        }
        r++;
        std::reverse(a + l, a + r);
        for (int j = l; j < r; j++) {
            b[a[j]] = j;
            pr[j + 1] = pr[j] + p[a[j]].w;
            update(0, 0, n + 1, j + 1);
        }
        que.push_back({ l, r });
        if (i + 1 == it || crossp(q[id].v, q[c[i + 1]].v) != 0) {
            std::sort(que.begin(), que.end());
            for (int j = 0; j < que.size(); j++) {
                l = que[j].first;
                r = que[j].second;
                s = getmin(0, 0, n + 1, 0, l + 1);
                for (int h = l; h < r; h++) {
                    ans = std::max(ans, pr[h + 1] - s);
                    s = std::min(s, pr[h + 1]);
                }
            }
            if (!que.empty() && que.back().second != n) {
                s = getmin(0, 0, n + 1, 0, que.back().second + 1);
                long long temp = getmax(0, 0, n + 1, que.back().second + 1, n + 1);
                ans = std::max(ans, temp - s);
            }
            que.clear();
        }
    }
    std::cout << ans;
    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:168:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |             for (int j = 0; j < que.size(); j++) {
      |                             ~~^~~~~~~~~~~~

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