Submission #1139080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139080		Noproblem29	Bulldozer (JOI17_bulldozer)	C++20	100 / 100	646 ms	66288 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
#ifndef BADGNU
#pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=4100;
const int M=1<<13;
const int B=447;
const int mod=998244353;
const ll INF=1e18;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;

struct pt{
    int x,y;
    int w;
};
bool operator<(const pt&a,const pt&b){
    if(a.x==b.x){
        if(a.y==b.y){
            return a.w<b.w;
        }
        return a.y<b.y;
    }
    return a.x<b.x;
}
bool operator==(const pt&a,const pt&b){
    return (a.x==b.x)&&(a.y==b.y)&&(a.w==b.w);
}
struct upside{
    ll l[M],r[M],dif[M];
    int sz=(M>>1);
    void init(){
        for(int i=0;i<sz*2-1;i++){
            l[i]=INF;
            r[i]=-INF;
            dif[i]=0;
        }
    }
    void upd(int k,int x){
        k+=(sz-1);
        l[k]=x;
        r[k]=x;
        while(k>0){
            k=(k-1)>>1;
            r[k]=max(r[k*2+1],r[k*2+2]);
            l[k]=min(l[k*2+1],l[k*2+2]);
            dif[k]=max(dif[k*2+1],dif[k*2+2]);
            dif[k]=max(dif[k],r[k*2+2]-l[k*2+1]);
        }
    }
}seg;
int n;
pt A[N];
int p[N];
int pref[N];
void test(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>A[i].x>>A[i].y>>A[i].w;
    }
    sort(A+1,A+n+1);
    vector<array<int,4>>v;
    for(int i=1;i<=n;i++){
        pref[i]=pref[i-1]+A[i].w;
        p[i]=i;
        for(int j=i+1;j<=n;j++){
            if(A[i].x<A[j].x){
                v.push_back({A[i].y-A[j].y,A[j].x-A[i].x,i,j});
            }
        }
    }
    sort(v.begin(),v.end(),[](array<int,4>a,array<int,4>b){
        if(a[0]*b[1]==b[0]*a[1]){
            if(a[2]==b[2]){
                return a[3]>b[3];
            }
            return a[2]>b[2];
        }
        return a[0]*b[1]>b[0]*a[1];
    });
    seg.init();
    for(int i=0;i<=n;i++){
        seg.upd(i,pref[i]);
    }
    ll ans=seg.dif[0];
    for(int i=0;i<v.size();i++){
        auto [k,h,l,r]=v[i];
        pref[p[l]]+=pref[p[l]+1]-2*pref[p[l]]+pref[p[l]-1];
        seg.upd(p[l],pref[p[l]]);
        swap(p[l],p[r]);
        if(i+1==v.size()){
            ans=max(ans,seg.dif[0]);
            break;
        }
        auto [k2,h2,l2,r2]=v[i+1];
        if(k*h2!=k2*h){
            ans=max(ans,seg.dif[0]);
        }
    }
    cout<<ans<<'\n';

}
/*

*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    int t2=1;
    // cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
}

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