제출 #625559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625559		ansol4328	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1182 ms	79284 KiB

bulldozer

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

struct SegTree{
    struct node{
        ll L, R, sum, mx;
    };
    vector<node> tree;
    int base;
    SegTree(int a){
        for(base=1 ; base<a ; base<<=1);
        tree.resize(base*2);
        base--;
    }
    node add(node &lhs, node &rhs){
        node ret;
        ret.sum=lhs.sum+rhs.sum;
        ret.L=max(lhs.L,lhs.sum+rhs.L);
        ret.R=max(rhs.R,rhs.sum+lhs.R);
        ret.mx=max({lhs.R+rhs.L, lhs.mx, rhs.mx});
        return ret;
    }
    void updt(int i, ll v){
        tree[i+=base]={v,v,v,v};
        for(i>>=1 ; i ; i>>=1) tree[i]=add(tree[i*2],tree[i*2+1]);
    }
    ll qry(){ return tree[1].mx; }
};

struct frac{
    ll a, b;
    bool operator< (const frac &rhs) const{
        return a*rhs.b>rhs.a*b;
    }
    bool operator== (const frac &rhs) const{
        return a*rhs.b==rhs.a*b;
    }
};

struct line{
    frac slp;
    int p1, p2;
    bool operator< (const line &rhs) const{
        return slp<rhs.slp;
    }
};

struct uf{
    vector<int> p;
    vector<ll> w;
    uf(int a) : p(a+5,-1), w(a+5,0) {}
    int f(int a){ return p[a]==-1 ? a : p[a]=f(p[a]); }
    void u(int x, int y){
        x=f(x), y=f(y);
        if(x==y) return;
        p[x]=y; w[y]+=w[x];
    }
};

int N;
pair<P,ll> M[2005];
int id[2005], inv[2005];
//id = sorted state, inv = inverse of id
vector<line> lst;
vector<int> grp[2005];

void fastio(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
}

int main(){
    fastio();
    cin >> N;
    for(int i=1 ; i<=N ; i++){
        cin >> M[i].fi.fi >> M[i].fi.se >> M[i].se;
    }
    if(N==1){
        cout << max(0LL,M[1].se) << '\n'; return 0;
    }
    vector<frac> F;
    sort(M+1,M+1+N);
    for(int i=1 ; i<=N ; i++){
        for(int j=i+1 ; j<=N ; j++){
            lst.pb({{M[i].fi.se-M[j].fi.se, M[i].fi.fi-M[j].fi.fi},i,j});
            F.pb(lst.back().slp);
        }
    }
    sort(lst.begin(),lst.end());
    sort(F.begin(),F.end());
    F.erase(unique(F.begin(),F.end()),F.end());

    SegTree seg(N);
    uf T(N);
    for(int i=1 ; i<=N ; i++) seg.updt(i,M[i].se), id[i]=inv[i]=i, T.w[i]=M[i].se;
    int cur=0;
    ll ans=0;
    vector<bool> chk(N+5);
    vector<int> S;
    for(auto slp : F){
//        cout << slp.a << '/' << slp.b << ' ' ;
        S.clear();
        for(; cur<lst.size() && lst[cur].slp==slp ; cur++){
            //union
            T.u(lst[cur].p1,lst[cur].p2);
            if(!chk[lst[cur].p1]) chk[lst[cur].p1]=true, S.pb(lst[cur].p1);
            if(!chk[lst[cur].p2]) chk[lst[cur].p2]=true, S.pb(lst[cur].p2);
        }
        vector<int> tmp;
        for(int p : S){
            if(T.f(p)==p) tmp.pb(p), seg.updt(inv[p],T.w[p]);
            else seg.updt(inv[p],0);
            grp[T.f(p)].pb(inv[p]);
        }
        ans=max(ans,seg.qry());
//        cout << ans << ' ' << seg.qry() << '\n';

        //re-ordering
        for(int G : tmp){
            sort(grp[G].begin(),grp[G].end());
            // for(int t : grp[G]) cout << t << ' ';
            // cout << '\n';
            for(int i=0, j=(int)grp[G].size()-1 ; i<j ; i++, j--){
                int x=grp[G][i], y=grp[G][j];
                swap(inv[id[x]],inv[id[y]]);
                swap(id[x],id[y]);
            }
            grp[G].clear();
        }
        // for(int i=1 ; i<=N ; i++) cout << id[i] << ' ';
        // cout << '\n';
        //roll back
        for(int p : S){
            T.w[p]=M[p].se; T.p[p]=-1;
            chk[p]=false;
            seg.updt(inv[p],T.w[p]);
        }
        ans=max(ans,seg.qry());
//        assert(S.size()==2);
    }
    ans=max(ans,seg.qry());
    cout << ans;
    return 0;
}

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

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(; cur<lst.size() && lst[cur].slp==slp ; cur++){
      |               ~~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20