oj.uz

Submission #127549

# Submission time Handle Problem Language Result Execution time Memory
127549 2019-07-09T14:44:09 Z arnold518 Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 49980 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 636 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 6 ms 632 KB Output is correct
26 Correct 6 ms 632 KB Output is correct
27 Correct 6 ms 632 KB Output is correct
28 Correct 6 ms 632 KB Output is correct
29 Correct 6 ms 632 KB Output is correct
30 Correct 6 ms 632 KB Output is correct
31 Correct 6 ms 632 KB Output is correct
32 Correct 7 ms 632 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 6 ms 632 KB Output is correct
26 Correct 6 ms 632 KB Output is correct
27 Correct 6 ms 632 KB Output is correct
28 Correct 6 ms 632 KB Output is correct
29 Correct 6 ms 632 KB Output is correct
30 Correct 6 ms 632 KB Output is correct
31 Correct 6 ms 632 KB Output is correct
32 Correct 7 ms 632 KB Output is correct
33 Execution timed out 2048 ms 49980 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 6 ms 632 KB Output is correct
26 Correct 6 ms 632 KB Output is correct
27 Correct 6 ms 632 KB Output is correct
28 Correct 6 ms 632 KB Output is correct
29 Correct 6 ms 632 KB Output is correct
30 Correct 6 ms 632 KB Output is correct
31 Correct 6 ms 632 KB Output is correct
32 Correct 7 ms 632 KB Output is correct
33 Execution timed out 2048 ms 49980 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 636 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 6 ms 632 KB Output is correct
17 Correct 6 ms 632 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 6 ms 632 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 7 ms 632 KB Output is correct
25 Correct 7 ms 632 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 6 ms 632 KB Output is correct
37 Correct 6 ms 632 KB Output is correct
38 Correct 6 ms 632 KB Output is correct
39 Correct 6 ms 632 KB Output is correct
40 Correct 6 ms 632 KB Output is correct
41 Correct 6 ms 632 KB Output is correct
42 Correct 6 ms 632 KB Output is correct
43 Correct 6 ms 632 KB Output is correct
44 Correct 6 ms 632 KB Output is correct
45 Correct 6 ms 632 KB Output is correct
46 Correct 6 ms 632 KB Output is correct
47 Correct 7 ms 632 KB Output is correct
48 Execution timed out 2048 ms 49980 KB Time limit exceeded
49 Halted 0 ms 0 KB -