답안 #489655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489655	2021-11-23T14:49:40 Z	Alexandruabcde	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	954 ms	524292 KB

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;
}

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #489655

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 35.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 35.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0