Submission #1270397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270397		MMihalev	Bulldozer (JOI17_bulldozer)	C++20	80 / 100	866 ms	99352 KiB

bulldozer

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
using namespace std;
const int MAX_N=2e3+5;
const long long INF=(1LL<<62);
int n;
long long x[MAX_N];
long long y[MAX_N];
long long cost[MAX_N],ans;
int pos[MAX_N];
vector<pair<pair<long long,int>,long long>>order;
struct V
{
    long long pref,suf,sum,sub;
};
V tree[4*MAX_N];
void Update(int node,int l,int r,int idx,long long val)
{
    if(l==r)
    {
        tree[node].pref=val;tree[node].suf=val;tree[node].sum=val;tree[node].sub=val;
        return;
    }
    int mid=(l+r)/2;
    if(idx<=mid)Update(2*node,l,mid,idx,val);
    else Update(2*node+1,mid+1,r,idx,val);

    tree[node].sum=tree[2*node].sum+tree[2*node+1].sum;
    tree[node].pref=max(tree[2*node].pref,tree[2*node].sum+tree[2*node+1].pref);
    tree[node].suf=max(tree[2*node+1].suf,tree[2*node+1].sum+tree[2*node].suf);
    tree[node].sub=max(tree[2*node].sub,tree[2*node+1].sub);
    tree[node].sub=max(tree[node].sub,tree[2*node].suf+tree[2*node+1].pref);
}
long long query()
{
    return tree[1].sub;
}
vector<vector<int>>currentpoints;
void swp(int i,int j)
{
    Update(1,1,n,pos[i]+1,cost[j]);
    Update(1,1,n,pos[j]+1,cost[i]);
    swap(pos[i],pos[j]);
}
bool cmp(int i,int j)
{
    return pos[i]<pos[j];
}
void solvefor()
{
    ans=max(ans,query());
    for(auto current:currentpoints)
    {
        sort(current.begin(),current.end(),cmp);
        auto last=unique(current.begin(),current.end());current.erase(last,current.end());
        for(int i=0;i<current.size()/2;i++)
        {
            swp(current[i],current[current.size()-1-i]);
        }
    }
    ans=max(ans,query());
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        order.push_back({{x[i],-y[i]},cost[i]});
    }

    sort(order.begin(),order.end());

    for(int i=0;i<n;i++)
    {
        Update(1,1,n,i+1,order[i].second);

        for(int idx=1;idx<=n;idx++)
        {
            if(order[i].first.first==x[idx] && -order[i].first.second==y[idx])
            {
                pos[idx]=i;
                break;
            }
        }
    }

    ans=0;

    vector<pair<pair<long double,long long>,pair<int,int>>>lines;

    unordered_map<long long,unordered_map<int,bool>>horizontalstuff;

    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            long double A=(long double)(((long double)y[i])-((long double)y[j]));
            long double B=(long double)(((long double)x[j])-((long double)x[i]));
            //long double C=-A*x[i]-B*y[i];
            if(B==0.0)
            {
                long long C=x[i];
                horizontalstuff[C][i]=1;
                horizontalstuff[C][j]=1;
                continue;
            }

            long long C=-A*x[i]-B*y[i];

            lines.push_back({{-(A/B),C},{i,j}});
        }
    }
    sort(lines.begin(),lines.end());

    vector<int>current;

    for(auto&[C,idxes]:horizontalstuff)
    {
        current.clear();
        for(auto&[idx,val]:idxes)
        {
            current.push_back(idx);
        }
        currentpoints.push_back(current);
    }
    solvefor();

    if(lines.size()==0){cout<<ans<<"\n";return;}

    currentpoints.clear();current.clear();
    current.push_back(lines[0].second.first);current.push_back(lines[0].second.second);
    for(int i=1;i<lines.size();i++)
    {
        if(lines[i].first.first==lines[i-1].first.first && lines[i].first.second==lines[i-1].first.second)
        {
            ;
        }
        else if(lines[i].first.first==lines[i-1].first.first)
        {
            currentpoints.push_back(current);current.clear();
        }
        else
        {
            currentpoints.push_back(current);
            solvefor();
            currentpoints.clear();current.clear();
        }
        current.push_back(lines[i].second.first);current.push_back(lines[i].second.second);
    }
    currentpoints.push_back(current);
    solvefor();

    cout<<ans<<"\n";
}
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i]>>cost[i];
    }
    solve();
    return 0;
}

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