Submission #1185279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185279		vnedu	Bulldozer (JOI17_bulldozer)	C++20	5 / 100	0 ms	328 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;
}
map<double,ii> 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[i].w);
//    }
//    maximize(ans,segtree.get());
//    for(int i=1;i<=ptr;)
//    {
//        double val=s[i].slope;
//        map<double,ii>().swap(mp);
//        while(i<=ptr && s[i].slope==val)
//        {
//            int mn=min(pos[s[i].i],pos[s[i].j]);
//            int mx=max(pos[s[i].i],pos[s[i].j]);
//            int id=s[i].i;
//            double slope=point[id].y-val*point[id].x;
//            if(!mp.count(slope)) mp[slope]=make_pair(mn,mx);
//            else
//            {
//                minimize(mp[slope].fi,mn);
//                maximize(mp[slope].se,mx);
//            }
//            ++i;
//        }
//        for(auto it : mp)
//        {
//            int l=it.se.fi;
//            int r=it.se.se;
//            for(int i=l;i<=r;++i)
//            {
//                b[i]=g[r-i+l];
//            }
//            for(int i=l;i<=r;++i)
//            {
//                segtree.update(1,1,n,i,point[b[i]].w);
//                swap(b[i],g[i]);
//                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: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20