oj.uz

Submission #270345

# Submission time Handle Problem Language Result Execution time Memory
270345 2020-08-17T14:19:55 Z MKopchev Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 215348 KB 
#include<bits/stdc++.h>
using namespace std;

const int nmax=2e3+42;

struct info
{
    long long x,y,gain;
};

int n;

info inp[nmax];

vector< pair<long long,long long> > seen,other;

bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
    return a.first*b.second<a.second*b.first;
}

void extend()
{
    for(int i=1;i<seen.size();i++)
    {
        long long up=seen[i].first+seen[i-1].first;
        long long down=seen[i].second+seen[i-1].second;

        long long g=__gcd(up,down);

        up=up/g;
        down=down/g;

        other.push_back({up,down});
    }

    for(auto k:other)seen.push_back(k);

    seen.push_back({seen.back().first+1,seen.back().second});
    seen.insert(seen.begin(),{seen[0].first-1,seen[0].second});
}

pair<long long,long long> cur;

bool eq(info u,info v)
{
    return (u.x-v.x)*cur.second==cur.first*(u.y-v.y);
}


bool cmp_2(info u,info v)
{
    return (u.x-v.x)*cur.second<cur.first*(u.y-v.y);
}
long long solve(pair<long long,long long> a)
{
    cur=a;

    sort(inp+1,inp+n+1,cmp_2);

    long long ret=0,cur_best=0,sum_now=0;

    for(int i=1;i<=n;i++)
    {
        sum_now+=inp[i].gain;

        if(eq(inp[i],inp[i+1])==0||i==n)
        {
            cur_best=max(cur_best+sum_now,sum_now);
            sum_now=0;
        }

        ret=max(ret,cur_best);
    }
    return ret;
}

struct line
{
    int i,j;
    long long up;
    long long down;
};

vector<line> all,help;

bool eq_line(line u,line v)
{
    return u.up*v.down==u.down*v.up;
}

bool cmp_line(line a,line b)
{
    if(a.up*b.down!=a.down*b.up)return a.up*b.down<a.down*b.up;
    if(a.j!=b.j)return a.j>b.j;
    return a.i>b.i;
}

struct mem
{
    long long sum,mx_pref,mx_suff,mx_interval;
};

mem tree[4*nmax];

mem my_merge(mem a,mem b)
{
    mem ret;
    ret.sum=a.sum+b.sum;
    ret.mx_pref=max(a.mx_pref,a.sum+b.mx_pref);
    ret.mx_suff=max(b.mx_suff,b.sum+a.mx_suff);

    ret.mx_interval=max(a.mx_interval,b.mx_interval);
    ret.mx_interval=max(ret.mx_interval,a.mx_suff+b.mx_pref);
    return ret;
}
void update(int node,int l,int r,int pos,long long add)
{
    if(l==r)
    {
        tree[node].sum+=add;
        tree[node].mx_pref=max(tree[node].sum,0LL);
        tree[node].mx_suff=max(tree[node].sum,0LL);
        tree[node].mx_interval=max(tree[node].sum,0LL);
        return;
    }

    int av=(l+r)/2;

    if(pos<=av)update(node*2,l,av,pos,add);
    else update(node*2+1,av+1,r,pos,add);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

int where[nmax];

int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld",&inp[i].x,&inp[i].y,&inp[i].gain);

    if(n==1)
    {
        printf("%lld\n",max(0LL,inp[1].gain));
        return 0;
    }

    seen.push_back({0,1});

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            long long up=inp[i].x-inp[j].x;
            long long down=inp[i].y-inp[j].y;

            if(down)
            {
                long long g=__gcd(abs(up),abs(down));

                up=up/g;
                down=down/g;

                if(down<0)down=-down,up=-up;

                seen.push_back({up,down});
            }
        }

    sort(seen.begin(),seen.end(),cmp);
    unique(seen.begin(),seen.end());

    extend();

    long long outp=0;

    outp=max(outp,solve(seen[0]));

    //cout<<"174 -> "<<outp<<endl;

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            line cur;
            cur.i=i;
            cur.j=j;

            long long up=inp[i].x-inp[j].x;
            long long down=inp[i].y-inp[j].y;

            if(down)
            {
                long long g=__gcd(abs(up),abs(down));

                up=up/g;
                down=down/g;

                if(down<0)down=-down,up=-up;

                cur.up=up;
                cur.down=down;

                all.push_back(cur);
            }
        }

    //cout<<"created "<<202<<" "<<all.size()<<endl;

    if(all.size())
    {
    sort(all.begin(),all.end(),cmp_line);

    help.push_back(all[0]);

    for(auto k:all)
        if(k.i!=help.back().i||k.j!=help.back().j)help.push_back(k);

    all=help;
    }

    for(int i=1;i<=n;i++)
    {
        where[i]=i;
        update(1,1,n,i,inp[i].gain);
    }

    //cout<<215<<" -> "<<all.size()<<endl;

    for(int i=0;i<all.size();i++)
    {
        int j=i;

        for(j=i;j<all.size()&&eq_line(all[i],all[j]);j++)
        {
        int le=where[all[j].i];
        int ri=where[all[j].j];
        /*
        cout<<all[j].i<<" "<<all[j].j<<" -> "<<le<<" "<<ri<<" "<<all[j].up<<" "<<all[j].down<<endl;
        for(int t=1;t<=n;t++)cout<<where[t]<<" ";cout<<endl;
        */
        assert(abs(le-ri)==1);

        update(1,1,n,le,-inp[le].gain);
        update(1,1,n,ri,-inp[ri].gain);

        swap(where[all[j].i],where[all[j].j]);
        swap(inp[le],inp[ri]);

        update(1,1,n,le,+inp[le].gain);
        update(1,1,n,ri,+inp[ri].gain);
        }

        i=j-1;

        outp=max(outp,tree[1].mx_interval);
    }

    printf("%lld\n",outp);
    return 0;
}

Compilation message

bulldozer.cpp: In function 'void extend()':
bulldozer.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=1;i<seen.size();i++)
      |                 ~^~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:230:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |     for(int i=0;i<all.size();i++)
      |                 ~^~~~~~~~~~~
bulldozer.cpp:234:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  234 |         for(j=i;j<all.size()&&eq_line(all[i],all[j]);j++)
      |                 ~^~~~~~~~~~~
bulldozer.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
bulldozer.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |         scanf("%lld%lld%lld",&inp[i].x,&inp[i].y,&inp[i].gain);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 956 KB Output is correct
2 Correct 8 ms 956 KB Output is correct
3 Correct 8 ms 1084 KB Output is correct
4 Correct 7 ms 988 KB Output is correct
5 Correct 7 ms 956 KB Output is correct
6 Correct 7 ms 956 KB Output is correct
7 Correct 7 ms 956 KB Output is correct
8 Correct 7 ms 956 KB Output is correct
9 Correct 7 ms 956 KB Output is correct
10 Correct 7 ms 956 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 6 ms 956 KB Output is correct
22 Correct 6 ms 956 KB Output is correct
23 Correct 6 ms 956 KB Output is correct
24 Correct 6 ms 956 KB Output is correct
25 Correct 7 ms 956 KB Output is correct
26 Correct 7 ms 1084 KB Output is correct
27 Correct 8 ms 1052 KB Output is correct
28 Correct 7 ms 996 KB Output is correct
29 Correct 7 ms 1004 KB Output is correct
30 Correct 6 ms 956 KB Output is correct
31 Correct 6 ms 956 KB Output is correct
32 Correct 7 ms 956 KB Output is correct
33 Execution timed out 2066 ms 215348 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 956 KB Output is correct
2 Correct 8 ms 956 KB Output is correct
3 Correct 8 ms 1084 KB Output is correct
4 Correct 7 ms 988 KB Output is correct
5 Correct 7 ms 956 KB Output is correct
6 Correct 7 ms 956 KB Output is correct
7 Correct 7 ms 956 KB Output is correct
8 Correct 7 ms 956 KB Output is correct
9 Correct 7 ms 956 KB Output is correct
10 Correct 7 ms 956 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 6 ms 956 KB Output is correct
22 Correct 6 ms 956 KB Output is correct
23 Correct 6 ms 956 KB Output is correct
24 Correct 6 ms 956 KB Output is correct
25 Correct 7 ms 956 KB Output is correct
26 Correct 7 ms 1084 KB Output is correct
27 Correct 8 ms 1052 KB Output is correct
28 Correct 7 ms 996 KB Output is correct
29 Correct 7 ms 1004 KB Output is correct
30 Correct 6 ms 956 KB Output is correct
31 Correct 6 ms 956 KB Output is correct
32 Correct 7 ms 956 KB Output is correct
33 Execution timed out 2066 ms 215348 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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