Submission #202896

#	Time	Username	Problem	Language	Result	Execution time	Memory
202896		moonrabbit2	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	6 ms	504 KiB

bulldozer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef vector<vector<ll>> mat;
const ll mod=998244353,inf=1e18;
const int N=2005,M=5e7+5,K=1e5+5;
struct st{
    ll dx,dy; int idx1,idx2;
}arr[N*N]; int cnt;
int n,rev[N];
ll s1,s2,ans;
struct point{
    ll x,y,c;
}a[N];
ll mx[4*N],s[4*N],ls[4*N],rs[4*N];
void upd(int nd,int l,int r,int x,ll v){
    if(l==r){
        s[nd]=v; mx[nd]=ls[nd]=rs[nd]=max(0ll,v);
        return;
    }
    int m=(l+r)>>1;
    if(x<=m) upd(nd<<1,l,m,x,v);
    else upd(nd<<1|1,m+1,r,x,v);
    s[nd]=s[nd<<1]+s[nd<<1|1];
    mx[nd]=max({mx[nd<<1],mx[nd<<1|1],rs[nd<<1]+ls[nd<<1|1]});
    ls[nd]=max(ls[nd<<1],s[nd<<1]+ls[nd<<1|1]);
    rs[nd]=max(rs[nd<<1|1],rs[nd<<1]+s[nd<<1|1]);
}
ll ccw(pll p1,pll p2,pll p3){
    return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+1+n,[](point p,point q){
        return pll(p.x,p.y)<pll(q.x,q.y);
    });
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            arr[++cnt]={a[j].x-a[i].x,a[j].y-a[i].y,i,j};
        }
    }
    sort(arr+1,arr+1+cnt,[](st p,st q){
        ll v=ccw(pll(0,0),pll(p.dx,p.dy),pll(q.dx,q.dy));
        if(v) return v>0;
        return pii(p.idx1,p.idx2)<pii(q.idx1,q.idx2);
    });
    for(int i=1;i<=n;i++){
        rev[i]=i;
        upd(1,1,n,i,a[i].c);
    }
    for(int i=1;i<=cnt;i++){
        int ii=i;
        while(ii+1<=n&&!ccw(pll(0,0),pll(arr[i].dx,arr[i].dy),pll(arr[ii+1].dx,arr[ii+1].dy))) ii++;
        for(int j=i;j<=ii;j++){
            int j1=arr[j].idx1,j2=arr[j].idx2;
            int k1=rev[j1],k2=rev[j2];
            swap(a[k1],a[k2]);
            swap(rev[j1],rev[j2]);
            upd(1,1,n,k1,a[k1].c);
            upd(1,1,n,k2,a[k2].c);
        }
        ans=max(ans,mx[1]);
        i=ii;
    }
    cout<<ans;
    return 0;
}

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