Submission #1030925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030925		tvladm2009	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	806 ms	50104 KiB

bulldozer

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

const int N = 5e5 + 7;

struct Point {
    ll x;
    ll y;
    ll cost;
};

bool cmp(Point a, Point b) {
    return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}

int n;
Point p[N];

struct Slope {
    ll y;
    ll x;
    int id1;
    int id2;
};

bool cmp_slope(Slope a, Slope b) {
    if (a.y * b.x == b.y * a.x) {
        return make_pair(a.id1, a.id2) < make_pair(b.id1, b.id2);
    }
    return a.y * b.x < b.y * a.x;
}

vector<Slope> v;
int pos[N];

struct Node {
    ll sum;
    ll pref;
    ll suff;
    ll ssm;
};

Node segt[4 * N];

Node operator + (Node a, Node b) {
    Node c;
    c.sum = a.sum + b.sum;
    c.pref = max(a.pref, a.sum + b.pref);
    c.suff = max(b.suff, b.sum + a.suff);
    c.ssm = max(a.ssm, b.ssm);
    c.ssm = max(c.ssm, a.suff + b.pref);
    return c;
}

void update(int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        segt[v].sum = x;
        segt[v].pref = x;
        segt[v].suff = x;
        segt[v].ssm = x;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update(2 * v, tl, tm, pos, x);
        } else {
            update(2 * v + 1, tm + 1, tr, pos, x);
        }
        segt[v] = segt[2 * v] + segt[2 * v + 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i].x >> p[i].y >> p[i].cost;
    }
    sort(p + 1, p + n + 1, cmp);

    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            Slope aux;
            aux.y = p[j].y - p[i].y;
            aux.x = p[j].x - p[i].x;
            aux.id1 = i;
            aux.id2 =j;
            v.push_back(aux);
        }
    }
    sort(v.begin(), v.end(), cmp_slope);

    for (int i = 1; i <= n; ++i) {
        pos[i] = i;
        update(1, 1, n, i, p[i].cost);
    }
    ll ans = max(0LL, segt[1].ssm);
    for (int i = 0; i < v.size(); ++i) {
        int j = i;
        while (j < v.size() && v[i].y * v[j].x == v[i].x * v[j].y) {
            update(1, 1, n, pos[v[j].id1], p[v[j].id2].cost);
            update(1, 1, n, pos[v[j].id2], p[v[j].id1].cost);
            swap(pos[v[j].id1], pos[v[j].id2]);
            j++;
        }
        ans = max(ans, segt[1].ssm);
        i = j - 1;
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Slope>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i < v.size(); ++i) {
      |                     ~~^~~~~~~~~~
bulldozer.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Slope>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         while (j < v.size() && v[i].y * v[j].x == v[i].x * v[j].y) {
      |                ~~^~~~~~~~~~

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