Submission #146409

#	Time	Username	Problem	Language	Result	Execution time	Memory
146409		osaaateiasavtnl	Bulldozer (JOI17_bulldozer)	C++14	75 / 100	999 ms	50120 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
const int N = 2007;
int n, ans = 0;
struct Point { 
    int x, y, c; 
    bool operator < (Point p) { return y < p.y; }
} a[N];
namespace TREE {
struct Node {
    int l, r, sum, ans;
    Node (int x) {
        sum = x;
        l = r = ans = max(0ll, x);
    }
    Node () {}
};  
Node merge(Node l, Node r) {
    Node ans;
    ans.sum = l.sum + r.sum;
    ans.l = max(l.l, l.sum + r.l);
    ans.r = max(r.r, r.sum + l.r);
    ans.ans = max(max(l.ans, r.ans), l.r + r.l);
    return ans;
}
Node tree[N << 2];
void build(int v, int tl, int tr) {
    if (tl == tr) { tree[v] = Node(a[tl].c); return; }
    int tm = (tl + tr) >> 1;
    build(v * 2 + 1, tl, tm); build(v * 2 + 2, tm + 1, tr);
    tree[v] = merge(tree[v * 2 + 1], tree[v * 2 + 2]);
}
void upd(int v, int tl, int tr, int p, int x) {
    if (tl == tr) { tree[v] = Node(x); return; }
    int tm = (tl + tr) >> 1;
    if (p <= tm) upd(v * 2 + 1, tl, tm, p, x);
    else upd(v * 2 + 2, tm + 1, tr, p, x);
    tree[v] = merge(tree[v * 2 + 1], tree[v * 2 + 2]);
}
void build() { build(0, 0, n - 1); }
void upd(int p, int x) { upd(0, 0, n - 1, p, x); }  
void relax() { ans = max(ans, tree[0].ans); }
};
struct Line {
    double ang; int i, j;
    bool operator < (Line l) { return ang < l.ang; }
};  
int pos[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    using namespace TREE;
    cin >> n; for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y >> a[i].c;
    sort(a, a + n); build(); relax();
    vector <Line> l;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (a[i].x == a[j].x && a[i].y == a[j].y) exit(1);
            l.app({atan2(a[j].y - a[i].y, a[j].x - a[i].x), i, j});
        }
    }
    for (int i = 0; i < n; ++i) pos[i] = i;
    sort(all(l));
    int ptr = 0;
    while (ptr < l.size()) {
        auto ang = l[ptr].ang;
        while (l[ptr].ang == ang) {
            auto &e = l[ptr];
            upd(pos[e.i], a[e.j].c);
            upd(pos[e.j], a[e.i].c);
            swap(pos[e.i], pos[e.j]);
            ++ptr;
        }
        #ifdef HOME
        vector <int> t(n);
        for (int i = 0; i < n; ++i) t[pos[i]] = a[i].c;
        for (int i = 0; i < n; ++i) cout << t[i] << ' ';
        cout << ": " << tree[0].ans << '\n';
        #endif
        relax();
    }
    cout << ans << '\n';
}   

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ptr < l.size()) {
            ~~~~^~~~~~~~~~

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