Submission #127549

#	Time	Username	Problem	Language	Result	Execution time	Memory
127549		arnold518	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2048 ms	49980 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;
    int m1, m2;
};

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

ll val[4*MAXN+10], lsum[4*MAXN+10], rsum[4*MAXN+10], sum[4*MAXN+10];

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

    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];
    val[node]=max(max(0ll, rsum[node*2]+lsum[node*2+1]), max(val[node*2], val[node*2+1]));
}

ll query() { return val[1]; }

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;
        update(1, 1, n, i, mine[i].w);
    }
    ans=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, 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)
        {
            return q.x*p.y<p.x*q.y;
        });

    for(i=0; i<L.size(); )
    {
        ll x=L[i].x, y=L[i].y;
        while(i<L.size() && L[i].x*y==L[i].y*x)
        {
            int m1=L[i].m1, m2=L[i].m2;

            update(1, 1, n, pos[m2], -mine[m2].w);
            pos[m2]--;
            update(1, 1, n, pos[m2], mine[m2].w);

            update(1, 1, n, pos[m1], -mine[m1].w);
            pos[m1]++;
            update(1, 1, n, pos[m1], mine[m1].w);
            i++;
        }
        ans=max(ans, query());
    }
    printf("%lld", ans);
}

Compilation message (stderr)

bulldozer.cpp: In function 'void update(int, int, int, int, ll)':
bulldozer.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<L.size(); )
              ~^~~~~~~~~
bulldozer.cpp:86: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:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
bulldozer.cpp:55: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: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20