oj.uz

Submission #125643

# Submission time Handle Problem Language Result Execution time Memory
125643 2019-07-06T06:58:03 Z arnold518 Bulldozer (JOI17_bulldozer) C++14
5 / 100
 3 ms 632 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;

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, i, j};
        if(now.x<0) now.x*=-1, now.y*=-1;
    }
    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(); i++)
    {
        ll m1=L[i].m1, m2=L[i].m2;
        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

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:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<L.size(); i++)
              ~^~~~~~~~~
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.0 / 5.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 632 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Incorrect 2 ms 572 KB Output isn't correct
17 Halted 0 ms 0 KB -