Submission #125729

#	Time	Username	Problem	Language	Result	Execution time	Memory
125729		arnold518	Bulldozer (JOI17_bulldozer)	C++14	80 / 100	1509 ms	71380 KiB

bulldozer

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;

struct Mine
{
    ll x, y, w;
};

struct Line
{
    ll x, y, z;
    int m1, m2;
};

int n, pos[MAXN+10];
Mine mine[MAXN+10];
ll arr[MAXN+10], ans;

struct SEG
{
    ll ans[4*MAXN+10], lsum[4*MAXN+10], rsum[4*MAXN+10], sum[4*MAXN+10];

    SEG()
    {
        memset(ans, 0, sizeof(ans));
        memset(lsum, 0, sizeof(lsum));
        memset(rsum, 0, sizeof(rsum));
        memset(sum, 0, sizeof(sum));
    }

    void update(int node, int tl, int tr, int pos, ll val)
    {
        if(tl==tr)
        {
            ans[node]=max(0ll, val);
            lsum[node]=max(0ll, val);
            rsum[node]=max(0ll, val);
            sum[node]=val;
            return;
        }
        int mid=tl+tr>>1;
        if(pos<=mid) update(node*2, tl, mid, pos, val);
        else update(node*2+1, mid+1, tr, pos, val);

        lsum[node]=max(lsum[node*2], sum[node*2]+lsum[node*2+1]);
        rsum[node]=max(rsum[node*2+1], sum[node*2+1]+rsum[node*2]);
        sum[node]=sum[node*2]+sum[node*2+1];
        ans[node]=max(max(0ll, rsum[node*2]+lsum[node*2+1]), max(ans[node*2], ans[node*2+1]));
    }

    ll query()
    {
        return ans[1];
    }
};
SEG seg;

int main()
{
    int i, j;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%lld%lld%lld", &mine[i].x, &mine[i].y, &mine[i].w);
    sort(mine+1, mine+n+1, [&](const Mine p, const Mine q)
        {
            if(p.x!=q.x) return p.x<q.x;
            return p.y<q.y;
        });

    for(i=1; i<=n; i++)
    {
        pos[i]=i;
        arr[i]=mine[i].w;
        seg.update(1, 1, n, i, mine[i].w);
    }
    ans=seg.query();

    vector<Line> L;
    for(i=1; i<=n; i++) for(j=i+1; j<=n; j++)
    {
        Line now={mine[i].x-mine[j].x, mine[i].y-mine[j].y, mine[i].y*mine[j].x-mine[j].y*mine[i].x, i, j};
        if(now.x<0) now.x*=-1, now.y*=-1;
        if(now.x==0 && now.y<0) now.y*=-1;
        L.push_back(now);
    }
    sort(L.begin(), L.end(), [&](const Line p, const Line q)
        {
            if(q.x*p.y!=p.x*q.y) return q.x*p.y<p.x*q.y;
            if(q.x*p.z!=p.x*q.z) return q.x*p.z<p.x*q.z;
            if(mine[p.m1].x!=mine[q.m1].x) return mine[p.m1].x<mine[q.m1].x;
            return mine[p.m1].y<mine[q.m1].y;
        });

    for(i=0; i<L.size(); )
    {
        ll x=L[i].x, y=L[i].y, z=L[i].z;
        while(i<L.size() && L[i].x*y==L[i].y*x)
        {
            x=L[i].x, y=L[i].y, z=L[i].z;
            vector<int> todo;
            while(i<L.size() && L[i].x*z==L[i].z*x)
            {
                todo.push_back(L[i].m1);
                todo.push_back(L[i].m2);
                i++;
            }
            sort(todo.begin(), todo.end());
            todo.erase(unique(todo.begin(), todo.end()), todo.end());
            for(j=0; j<todo.size()/2; j++)
            {
                int m1=todo[j], m2=todo[todo.size()-j-1];
                seg.update(1, 1, n, pos[m1], arr[pos[m2]]);
                seg.update(1, 1, n, pos[m2], arr[pos[m1]]);
                swap(arr[pos[m1]], arr[pos[m2]]);
                swap(pos[m1], pos[m2]);
            }
        }
        ans=max(ans, seg.query());
    }
    printf("%lld", ans);
}

Compilation message (stderr)

bulldozer.cpp: In member function 'void SEG::update(int, int, int, int, ll)':
bulldozer.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<L.size(); )
              ~^~~~~~~~~
bulldozer.cpp:103:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i<L.size() && L[i].x*y==L[i].y*x)
               ~^~~~~~~~~
bulldozer.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(i<L.size() && L[i].x*z==L[i].z*x)
                   ~^~~~~~~~~
bulldozer.cpp:115:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0; j<todo.size()/2; j++)
                      ~^~~~~~~~~~~~~~
bulldozer.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
bulldozer.cpp:69:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=n; i++) scanf("%lld%lld%lld", &mine[i].x, &mine[i].y, &mine[i].w);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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