제출 #489655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489655		Alexandruabcde	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	954 ms	524292 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;
    LL best;

    Node* st;
    Node* dr;

    Node (LL val) {
        sum = pref = suff = best = val;
        st = dr = nullptr;
    }
};

Node* arb = nullptr;

Node* Combine (Node* a, Node* b) {
    Node* rez = new Node(0);
    rez->st = a;
    rez->dr = b;

    if (a == nullptr)
        a = new Node(0);
    if (b == nullptr)
        b = new Node(0);

    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 (Node* &Tree, int a, int b, int poz, LL val) {
    if (Tree == nullptr)
        Tree = new Node(0);

    if (a == b) {
        Tree = new Node(val);
        return;
    }

    int mij = (a + b) / 2;

    if (poz <= mij) Update(Tree->st, a, mij, poz, val);
    else Update(Tree->dr, mij+1, b, poz, val);

    Tree = Combine(Tree->st, Tree->dr);
}

void Traversez (Node* Tree, int a, int b) {
    if (Tree == nullptr) return;

    int mij = (a + b) / 2;
    Traversez(Tree->st, a, mij);
    Traversez(Tree->dr, mij+1, b);
}
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(arb, 1, N, i, P[i].cost);
    }
    LL sol = max(0LL, arb->best);
    Traversez(arb, 1, N);

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

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

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

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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