oj.uz

Submission #476762

# Submission time Handle Problem Language Result Execution time Memory
476762 2021-09-28T13:33:00 Z nicolaalexandra Bulldozer (JOI17_bulldozer) C++14
25 / 100
 3 ms 604 KB 
#include <bits/stdc++.h>
#define DIM 1010
#define INF 2000000000
using namespace std;

struct punct{
    long long x,y,cost;
} v[DIM];

struct panta{
    long long a,b;
    int idx,idx2;
};

vector <panta> p;

struct segment_tree{
    long long best,pref,suf,sum;
} aint[DIM*4];

int n,i,j,k;
long long sol;
int poz[DIM];

void update_nod (int nod){
    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    aint[nod].sum = aint[fiu_st].sum + aint[fiu_dr].sum;
    aint[nod].pref = max (aint[fiu_st].pref, aint[fiu_st].sum + aint[fiu_dr].pref);
    aint[nod].suf = max (aint[fiu_dr].suf,aint[fiu_dr].sum + aint[fiu_st].suf);
    aint[nod].best = max (aint[fiu_st].best,aint[fiu_dr].best);
    aint[nod].best = max (aint[nod].best,aint[fiu_st].suf + aint[fiu_dr].pref);
    aint[nod].best = max (aint[nod].best,max(aint[nod].pref,aint[nod].suf));
}

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].sum = v[st].cost;
        aint[nod].pref = v[st].cost;
        aint[nod].suf = v[st].cost;
        aint[nod].best = v[st].cost;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    update_nod(nod);
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod].sum = val;
        aint[nod].pref = val;
        aint[nod].suf = val;
        aint[nod].best = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    update_nod(nod);
}


inline int cmp (punct a, punct b){
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

inline int cmp2 (panta p1, panta p2){

    if (p1.a * p2.b == p1.b * p2.a){
        if (p1.idx == p2.idx)
            return p1.idx2 < p2.idx2;
        return p1.idx < p2.idx;
    }

    return p1.a * p2.b < p1.b * p2.a;

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>v[i].x>>v[i].y>>v[i].cost;

    sort (v+1,v+n+1,cmp);

    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++)
            p.push_back({v[j].y-v[i].y,v[j].x-v[i].x,i,j});

    sort (p.begin(),p.end(),cmp2);


    for (i=1;i<=n;i++)
        poz[i] = i;

    build (1,1,n);

    sol = max(0LL,aint[1].best);

    i = 0;
    while (i < p.size()){

        j = i;
        while (j < p.size() && p[i].a * p[j].b == p[i].b * p[j].a){

            update (1,1,n,poz[p[j].idx2], v[ p[j].idx ].cost);

            update (1,1,n,poz[p[j].idx],v[ p[j].idx2 ].cost);

            swap (poz[p[j].idx],poz[p[j].idx2]);

            j++;
        }

        sol = max (sol,aint[1].best);
        i = j;

    }

    cout<<sol;


    return 0;
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:110:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<panta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     while (i < p.size()){
      |            ~~^~~~~~~~~~
bulldozer.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<panta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         while (j < p.size() && p[i].a * p[j].b == p[i].b * p[j].a){
      |                ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 1 ms 224 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 304 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 2 ms 556 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 2 ms 588 KB Output is correct
27 Correct 2 ms 588 KB Output is correct
28 Correct 3 ms 604 KB Output is correct
29 Correct 3 ms 588 KB Output is correct
30 Correct 2 ms 588 KB Output is correct
31 Correct 3 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 1 ms 224 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 304 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 2 ms 556 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 2 ms 588 KB Output is correct
27 Correct 2 ms 588 KB Output is correct
28 Correct 3 ms 604 KB Output is correct
29 Correct 3 ms 588 KB Output is correct
30 Correct 2 ms 588 KB Output is correct
31 Correct 3 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct
33 Runtime error 2 ms 520 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 1 ms 224 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 304 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 2 ms 556 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 2 ms 588 KB Output is correct
27 Correct 2 ms 588 KB Output is correct
28 Correct 3 ms 604 KB Output is correct
29 Correct 3 ms 588 KB Output is correct
30 Correct 2 ms 588 KB Output is correct
31 Correct 3 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct
33 Runtime error 2 ms 520 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 3 ms 588 KB Output is correct
20 Correct 3 ms 588 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 3 ms 588 KB Output is correct
23 Correct 3 ms 588 KB Output is correct
24 Correct 3 ms 588 KB Output is correct
25 Correct 3 ms 588 KB Output is correct
26 Correct 1 ms 224 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 0 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 0 ms 304 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 2 ms 588 KB Output is correct
37 Correct 2 ms 556 KB Output is correct
38 Correct 2 ms 588 KB Output is correct
39 Correct 2 ms 588 KB Output is correct
40 Correct 2 ms 588 KB Output is correct
41 Correct 2 ms 588 KB Output is correct
42 Correct 2 ms 588 KB Output is correct
43 Correct 3 ms 604 KB Output is correct
44 Correct 3 ms 588 KB Output is correct
45 Correct 2 ms 588 KB Output is correct
46 Correct 3 ms 588 KB Output is correct
47 Correct 2 ms 588 KB Output is correct
48 Runtime error 2 ms 520 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -