Submission #1185296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185296		vnedu	Bulldozer (JOI17_bulldozer)	C++20	80 / 100	699 ms	32024 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 2e3 + 10;
const double inf=INT_MAX-10;
struct segTree
{
    struct node
    {
        ll mx,p,s,sum;
        node() {}
        node(ll val) : mx(val),p(val),s(val),sum(val) {}

        node operator * (const node &S) const
        {
            node ans;
            ans.sum=sum+S.sum;
            ans.p=max(p,sum+S.p);
            ans.s=max(S.s,S.sum+s);
            ans.mx=max({mx,S.mx,s+S.p});
            return ans;
        }
    } t[N<<2];
    segTree() {}
    void update(int id, int l, int r, int x, ll val)
    {
        if(l>x||r<x) return;
        if(l==r) return void(t[id]=node(val));
        int mid((l+r)>>1);
        update(id<<1,l,mid,x,val);
        update(id<<1|1,mid+1,r,x,val);
        t[id]=t[id<<1]*t[id<<1|1];
    }
    ll get()
    {
        return t[1].mx;
    }
} segtree;
struct Point
{
    int x,y,w;
    Point() {}
    void input()
    {
        cin>>x>>y>>w;
    }
    double slope(const Point &S) const
    {
        return (y-S.y)*1.0/(x-S.x);
    }
    bool operator < (const Point &S) const
    {
        return x<S.x;
    }
} point[N];
struct Slope
{
    double slope;
    int i,j;
    Slope() {}
    Slope(double slope, int i, int j ) : slope(slope),i(i),j(j) {}
    bool operator < (const Slope &S) const
    {
        return slope<S.slope;
    }
} s[N*N/2];
int n,ptr=0,pos[N],g[N],b[N];
bool cmp(int i, int j)
{
    return point[i].y+inf*point[i].x<point[j].y+inf*point[j].x;
}
set<pair<double,int>> mp;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i) point[i].input();
    sort(point+1,point+1+n);
    ll ans=0,sum=0;
    for(int i=1;i<=n;)
    {
        int val=point[i].x;
        ll cur=0;
        while(i<=n && point[i].x==val)
        {
            cur+=point[i].w;
            ++i;
        }
        sum=max(0LL,sum)+cur;
        maximize(ans,sum);
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j && point[i].x>point[j].x) s[++ptr]=Slope(point[i].slope(point[j]),i,j);
    sort(s+1,s+1+ptr);
    for(int i=1;i<=n;++i) g[i]=i;
    sort(g+1,g+1+n,cmp);
    for(int i=1;i<=n;++i)
    {
        pos[g[i]]=i;
        segtree.update(1,1,n,i,point[g[i]].w);
    }
    maximize(ans,segtree.get());
    for(int i=1;i<=ptr;)
    {
        double val=s[i].slope;
        set<pair<double,int>>().swap(mp);
        while(i<=ptr && s[i].slope==val)
        {
            int id=s[i].i;
            double slope=point[id].y-val*point[id].x;
            mp.insert({slope,pos[s[i].i]});
            mp.insert({slope,pos[s[i].j]});
            ++i;
        }

        for(auto it=mp.begin(); it!=mp.end(); )
        {
            int l=(*it).se,r=l-1;
            double val=(*it).fi;
            while(it!=mp.end() && (*it).fi==val && (*it).se==r+1) ++r,++it;
            for(int i=l;i<=r;++i)
            {
                b[i]=g[r-i+l];
            }
            for(int i=l;i<=r;++i)
            {
                swap(b[i],g[i]);
                segtree.update(1,1,n,i,point[g[i]].w);
                pos[g[i]]=i;
            }
//            cout<<l<<' '<<r<<'\n';
        }
//        cout<<'\n';
        maximize(ans,segtree.get());
    }
    cout<<ans;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

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