Submission #489656

#	Time	Username	Problem	Language	Result	Execution time	Memory
489656		Alexandruabcde	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1010 ms	50080 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2005;
typedef long long LL;
constexpr LL INF = 1000000000000000000;

int N;

struct punct {
    LL x, y;
    LL cost;
};

bool cmp (punct a, punct b) {
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}

punct P[NMAX];

struct Panta {
    LL y, x;
    int ind_1, ind_2;
};

bool cmp_Panta (Panta a, Panta b) {
    if (a.y * b.x == b.y * a.x) {
        if (a.ind_1 == b.ind_1)
            return a.ind_2 < b.ind_2;
        return a.ind_1 < b.ind_1;
    }

    return (a.y * b.x < b.y * a.x);
}

vector <Panta> V;

int poz[NMAX];

struct Node {
    LL sum;
    LL pref, suff, best;
};
Node arbore[4*NMAX];

Node Combin (Node a, Node b) {
    Node rez;

    rez.sum = (a.sum + b.sum);
    rez.pref = max(a.pref, a.sum + b.pref);
    rez.suff = max(b.suff, b.sum + a.suff);
    rez.best = max(a.best, b.best);
    rez.best = max(rez.best, a.suff + b.pref);

    return rez;
}

void Update (int nod, int a, int b, int poz, LL val) {
    if (a == b) {
        arbore[nod].best = val;
        arbore[nod].pref = val;
        arbore[nod].suff = val;
        arbore[nod].sum = val;
        return;
    }

    int mij = (a + b) / 2;
    if (poz <= mij) Update(2*nod, a, mij, poz, val);
    else Update(2*nod+1, mij+1, b, poz, val);

    arbore[nod] = Combin(arbore[2*nod], arbore[2*nod+1]);
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    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 ) {
            Panta aux;
            aux.y = P[j].y - P[i].y;
            aux.x = P[j].x - P[i].x;
            aux.ind_1 = i;
            aux.ind_2 = j;
            V.push_back(aux);
        }
    sort(V.begin(), V.end(), cmp_Panta);
}

void Solve () {
    for (int i = 1; i <= N; ++ i ) {
        poz[i] = i;
        Update(1, 1, N, i, P[i].cost);
    }
    LL sol = max(0LL, arbore[1].best);

    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, poz[V[j].ind_1], P[V[j].ind_2].cost);
            Update(1, 1, N, poz[V[j].ind_2], P[V[j].ind_1].cost);

            swap(poz[V[j].ind_1], poz[V[j].ind_2]);
            ++ j;
        }

        sol = max(sol, arbore[1].best);
        i = j-1;
    }

    cout << sol << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'void Solve()':
bulldozer.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Panta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for (int i = 0; i < V.size(); ++ i ) {
      |                     ~~^~~~~~~~~~
bulldozer.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Panta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         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