제출 #476762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476762		nicolaalexandra	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	3 ms	604 KiB

bulldozer

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

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

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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20