oj.uz

답안 #476760

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476760 2021-09-28T13:31:19 Z nicolaalexandra Bulldozer (JOI17_bulldozer) C++14
0 / 100
 2 ms 528 KB 
#include <bits/stdc++.h>
#define DIM 1010
#define INF 2000000000
using namespace std;

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

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

vector <panta> p;

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

int n,i,j,k,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 = 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:108:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<panta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     while (i < p.size()){
      |            ~~^~~~~~~~~~
bulldozer.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<panta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         while (j < p.size() && p[i].a * p[j].b == p[i].b * p[j].a){
      |                ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 528 KB Output isn't correct
2 Halted 0 ms 0 KB -