Submission #1195134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195134		vnedu	Bulldozer (JOI17_bulldozer)	C++17	Compilation error	0 ms	0 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 ///

#define double long double

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;
    }
    ii slope(const Point &S) const
    {
        ll num=S.y-y;
        ll den=S.x-x;
        if(den<0) den*=-1,num*=-1;
        return make_pair(num,den);
    }
    bool operator < (const Point &S) const
    {
        return x<S.x;
    }
} point[N];
struct Slope
{
    ii fra;
    int i,j;
    Slope() {}
    Slope(ii fra, int i, int j ) : fra(fra),i(i),j(j) {}
    bool operator < (const Slope &S) const
    {
        return fra.fi*1LL*S.fra.se<fra.se*1LL*S.fra.fi;
    }
} 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+esp<point[j].y+inf*point[j].x;
}
set<pair<pair<ll,ll>,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;)
    {
        ii val=s[i].fra;
        mp.clear();
//        while(i<=ptr && abs(s[i].slope-val)<esp)
        while(i<=ptr && val.fi*1LL*s[i].fra.se==val.se*1LL*s[i].fra.fi)
        {
            int id=s[i].i;

//            double slope=point[id].y-val*point[id].x;
            pair<ll,ll> cm;
            cm.fi=-val.fi*1LL*point[id].x;
            cm.se=val.se;
            cm.fi+=point[id].y*1LL*cm.se;
            ll d=__gcd(max(cm.fi,-cm.fi),max(cm.se,-cm.se));
            cm.fi/=d;
            cm.se/=d;
            if(cm.se<0) cm.se*=-1,cm.fi*=-1;
            if(cm.fi==0) cm.se=1;
            mp.insert({cm,pos[s[i].i]});
            mp.insert({cm,pos[s[i].j]});
            ++i;
        }

        for(auto it=mp.begin(); it!=mp.end(); )
        {
            int l=(*it).se,r=l-1;
            pair<ll,ll> val=(*it).fi;
            while(it!=mp.end() && val==(*it).fi)
//            while(it!=mp.end() && (*it).fi==val)
            {
                ++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;
}

Compilation message (stderr)

bulldozer.cpp: In function 'bool cmp(int, int)':
bulldozer.cpp:91:38: error: 'esp' was not declared in this scope; did you mean 'exp'?
   91 |     return point[i].y+inf*point[i].x+esp<point[j].y+inf*point[j].x;
      |                                      ^~~
      |                                      exp