oj.uz

Submission #489655

# Submission time Handle Problem Language Result Execution time Memory
489655 2021-11-23T14:49:40 Z Alexandruabcde Bulldozer (JOI17_bulldozer) C++14
25 / 100
 954 ms 524292 KB 
#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;
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5264 KB Output is correct
2 Correct 5 ms 5276 KB Output is correct
3 Correct 4 ms 5264 KB Output is correct
4 Correct 5 ms 5264 KB Output is correct
5 Correct 5 ms 5232 KB Output is correct
6 Correct 5 ms 5264 KB Output is correct
7 Correct 5 ms 5312 KB Output is correct
8 Correct 5 ms 5264 KB Output is correct
9 Correct 5 ms 5264 KB Output is correct
10 Correct 4 ms 5252 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5264 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5264 KB Output is correct
4 Correct 6 ms 5264 KB Output is correct
5 Correct 5 ms 5300 KB Output is correct
6 Correct 5 ms 5292 KB Output is correct
7 Correct 5 ms 5264 KB Output is correct
8 Correct 5 ms 5264 KB Output is correct
9 Correct 5 ms 5264 KB Output is correct
10 Correct 5 ms 5264 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 0 ms 208 KB Output is correct
20 Correct 1 ms 208 KB Output is correct
21 Correct 6 ms 5264 KB Output is correct
22 Correct 5 ms 5264 KB Output is correct
23 Correct 6 ms 5204 KB Output is correct
24 Correct 5 ms 5256 KB Output is correct
25 Correct 5 ms 5264 KB Output is correct
26 Correct 5 ms 5264 KB Output is correct
27 Correct 5 ms 5264 KB Output is correct
28 Correct 5 ms 5264 KB Output is correct
29 Correct 8 ms 5252 KB Output is correct
30 Correct 6 ms 5264 KB Output is correct
31 Correct 5 ms 5264 KB Output is correct
32 Correct 5 ms 5264 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5264 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5264 KB Output is correct
4 Correct 6 ms 5264 KB Output is correct
5 Correct 5 ms 5300 KB Output is correct
6 Correct 5 ms 5292 KB Output is correct
7 Correct 5 ms 5264 KB Output is correct
8 Correct 5 ms 5264 KB Output is correct
9 Correct 5 ms 5264 KB Output is correct
10 Correct 5 ms 5264 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 0 ms 208 KB Output is correct
20 Correct 1 ms 208 KB Output is correct
21 Correct 6 ms 5264 KB Output is correct
22 Correct 5 ms 5264 KB Output is correct
23 Correct 6 ms 5204 KB Output is correct
24 Correct 5 ms 5256 KB Output is correct
25 Correct 5 ms 5264 KB Output is correct
26 Correct 5 ms 5264 KB Output is correct
27 Correct 5 ms 5264 KB Output is correct
28 Correct 5 ms 5264 KB Output is correct
29 Correct 8 ms 5252 KB Output is correct
30 Correct 6 ms 5264 KB Output is correct
31 Correct 5 ms 5264 KB Output is correct
32 Correct 5 ms 5264 KB Output is correct
33 Runtime error 954 ms 524292 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5264 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5264 KB Output is correct
4 Correct 6 ms 5264 KB Output is correct
5 Correct 5 ms 5300 KB Output is correct
6 Correct 5 ms 5292 KB Output is correct
7 Correct 5 ms 5264 KB Output is correct
8 Correct 5 ms 5264 KB Output is correct
9 Correct 5 ms 5264 KB Output is correct
10 Correct 5 ms 5264 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 0 ms 208 KB Output is correct
20 Correct 1 ms 208 KB Output is correct
21 Correct 6 ms 5264 KB Output is correct
22 Correct 5 ms 5264 KB Output is correct
23 Correct 6 ms 5204 KB Output is correct
24 Correct 5 ms 5256 KB Output is correct
25 Correct 5 ms 5264 KB Output is correct
26 Correct 5 ms 5264 KB Output is correct
27 Correct 5 ms 5264 KB Output is correct
28 Correct 5 ms 5264 KB Output is correct
29 Correct 8 ms 5252 KB Output is correct
30 Correct 6 ms 5264 KB Output is correct
31 Correct 5 ms 5264 KB Output is correct
32 Correct 5 ms 5264 KB Output is correct
33 Runtime error 954 ms 524292 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5264 KB Output is correct
2 Correct 5 ms 5276 KB Output is correct
3 Correct 4 ms 5264 KB Output is correct
4 Correct 5 ms 5264 KB Output is correct
5 Correct 5 ms 5232 KB Output is correct
6 Correct 5 ms 5264 KB Output is correct
7 Correct 5 ms 5312 KB Output is correct
8 Correct 5 ms 5264 KB Output is correct
9 Correct 5 ms 5264 KB Output is correct
10 Correct 4 ms 5252 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 9 ms 5264 KB Output is correct
17 Correct 6 ms 5248 KB Output is correct
18 Correct 6 ms 5264 KB Output is correct
19 Correct 6 ms 5264 KB Output is correct
20 Correct 5 ms 5300 KB Output is correct
21 Correct 5 ms 5292 KB Output is correct
22 Correct 5 ms 5264 KB Output is correct
23 Correct 5 ms 5264 KB Output is correct
24 Correct 5 ms 5264 KB Output is correct
25 Correct 5 ms 5264 KB Output is correct
26 Correct 0 ms 208 KB Output is correct
27 Correct 0 ms 208 KB Output is correct
28 Correct 0 ms 208 KB Output is correct
29 Correct 0 ms 208 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Correct 0 ms 208 KB Output is correct
35 Correct 1 ms 208 KB Output is correct
36 Correct 6 ms 5264 KB Output is correct
37 Correct 5 ms 5264 KB Output is correct
38 Correct 6 ms 5204 KB Output is correct
39 Correct 5 ms 5256 KB Output is correct
40 Correct 5 ms 5264 KB Output is correct
41 Correct 5 ms 5264 KB Output is correct
42 Correct 5 ms 5264 KB Output is correct
43 Correct 5 ms 5264 KB Output is correct
44 Correct 8 ms 5252 KB Output is correct
45 Correct 6 ms 5264 KB Output is correct
46 Correct 5 ms 5264 KB Output is correct
47 Correct 5 ms 5264 KB Output is correct
48 Runtime error 954 ms 524292 KB Execution killed with signal 9
49 Halted 0 ms 0 KB -