Submission #269960

#	Time	Username	Problem	Language	Result	Execution time	Memory
269960		MKopchev	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2059 ms	97716 KiB

bulldozer

#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;
}
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);

    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;

    for(auto k:seen)
        outp=max(outp,solve(k));

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

Compilation message (stderr)

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:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
bulldozer.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |         scanf("%lld%lld%lld",&inp[i].x,&inp[i].y,&inp[i].gain);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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