Submission #213174

#	Time	Username	Problem	Language	Result	Execution time	Memory
213174		HNO2	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	882 ms	66604 KiB

bulldozer

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

typedef long long ll;
const int maxn=2020;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define int ll

#ifdef HNO2
#define IOS
#else
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2

int n;

struct segtree
{
    int sum[maxn*4],lmax[maxn*4],rmax[maxn*4],maxx[maxn*4];

    void pull(int now)
    {
        sum[now]=sum[now*2]+sum[now*2+1];
        lmax[now]=max(lmax[now*2],sum[now*2]+lmax[now*2+1]);
        rmax[now]=max(rmax[now*2+1],sum[now*2+1]+rmax[now*2]);
        maxx[now]=max({maxx[now*2],maxx[now*2+1],rmax[now*2]+lmax[now*2+1]});
    }

    void modify(int now,int l,int r,int x,int v)
    {
        if (l==r)
        {
            sum[now]=lmax[now]=rmax[now]=maxx[now]=v;
            return;
        }
        int m=(l+r)>>1;
        if (x<=m) modify(now*2,l,m,x,v);
        else modify(now*2+1,m+1,r,x,v);
        pull(now);
    }

    int query()
    {
        return maxx[1];
    }
}tree;

struct frac
{
    int x,y;
    frac(int _x,int _y)
    {
        if (_x<0) _x=(-_x),_y=(-_y);
        x=_x,y=_y;
    }

    bool operator<(const frac &rhs)const
    {
        return y*rhs.x<x*rhs.y;
    }

    bool operator==(const frac &rhs)const
    {
        return y*rhs.x==x*rhs.y;
    }
};

int X[maxn],Y[maxn],C[maxn];
int p[maxn],att[maxn],c[maxn];

void Swap(int x,int y)
{
    swap(att[p[x]],att[p[y]]);
    swap(c[x],c[y]);
    swap(p[x],p[y]);
    tree.modify(1,1,n,x,c[x]);
    tree.modify(1,1,n,y,c[y]);
}

void rev(int l,int r)
{
    for (int i=l;i<=(l+r-1)/2;i++) Swap(i,l+r-i);
}

int32_t main()
{
    IOS
    vector<int> tmp;
    vector<pair<frac,pii> > v;

    cin>>n;
    for (int i=1;i<=n;i++)
    {
        tmp.pb(i);
        cin>>X[i]>>Y[i]>>C[i];
    }
    sort(all(tmp),[&](int i,int j)
         {
             if (X[i]!=X[j]) return X[i]<X[j];
             else return Y[i]<Y[j];
         });

    for (int i=0;i<n;i++)
    {
        p[i+1]=tmp[i];
        att[p[i+1]]=i+1;
        c[i+1]=C[p[i+1]];
        tree.modify(1,1,n,i+1,C[p[i+1]]);
    }

    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            if (X[i]!=X[j]) v.pb(mkp(frac(X[j]-X[i],Y[j]-Y[i]),mkp(i,j)));

    sort(all(v));
    reverse(all(v));

    int ans=max(0ll,tree.query());

    while (!v.empty())
    {
        frac last=v.back().F;
        vector<pii> ttmp;

        while (!v.empty()&&v.back().F==last)
            ttmp.pb(mkp(min(att[v.back().S.F],att[v.back().S.S]),max(att[v.back().S.F],att[v.back().S.S])))
                ,v.pop_back();
        sort(all(ttmp));
        reverse(all(ttmp));
        while (!ttmp.empty())
        {
            int tmpl=ttmp.back().F,tmpr=ttmp.back().F;
            while (!ttmp.empty()&&ttmp.back().F==tmpl)
            {
                tmpr++;
                ttmp.pop_back();
            }
            while (!ttmp.empty()&&ttmp.back().S<=tmpr) ttmp.pop_back();
            rev(tmpl,tmpr);
        }

        ans=max(ans,tree.query());
    }

    cout<<ans<<endl;
}

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