Submission #1079650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079650		danikoynov	Bulldozer (JOI17_bulldozer)	C++14	20 / 100	2041 ms	49844 KiB

bulldozer

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

struct Point
{
    ll x, y;
    
    Point(ll _x = 0, ll _y = 0)
    {
        x = _x;
        y = _y;
    }
    
    void input()
    {
        cin >> x >> y;
    }
};
    
const int MAXN = 2010;
int n;
pair < Point, ll > spot[MAXN];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        spot[i].first.input();
        cin >> spot[i].second;
    }
}

struct Fraction
{
    ll num, dev;

    Fraction(ll _num = 0, ll _dev = 0)
    {
        num = _num;
        dev = _dev;
    }

    void rationalize()
    {
        ll nod = __gcd(num, dev);
        if (nod < 0)
            nod = - nod;
        num /= nod;
        dev /= nod;
    }

    bool operator < (const Fraction f) const
    {
        /// num / dev < f.num / f.dev
        return (num * f.dev) < (f.num * dev);
    }
};


bool cmp(pair < Point, ll > p1, pair < Point, ll > p2)
{
    if (p1.first.x != p2.first.x)
        return p1.first.x < p2.first.x;
    return p1.first.y > p2.first.y;
}


int position[MAXN];
void simulate()
{
    if (n == 1)
    {
        ll result = 0;
        result = max(result, spot[1].second);
        cout << result << endl;
        return;
    }

    sort(spot + 1, spot + n + 1, cmp);
    for (int i = 1; i <= n; i ++)
        position[i] = i;

    vector < pair < Fraction, pair < int, int > > > events;
    for (int i = 1; i <= n; i ++)
        for (int j = i + 1; j <= n; j ++)
        {
            Fraction slope(spot[j].first.y - spot[i].first.y, 
                    spot[j].first.x - spot[i].first.x);
            slope.rationalize();
            events.push_back({slope, {i, j}});
        }

    sort(events.begin(), events.end());

    ll result = 0;
    for (pair < Fraction, pair < ll, ll > > event : events)
    {
        Fraction slope = event.first;
        pair < ll, ll > pivots = event.second;
        //cout << pivots.first << " : " << pivots.second << endl;
        assert(abs(position[pivots.first] - position[pivots.second]) == 1);
        swap(spot[position[pivots.first]], spot[position[pivots.second]]);
        swap(position[pivots.first], position[pivots.second]);
        ll sum = 0;
        for (int i = 1; i <= n; i ++)
        {
            sum += spot[i].second;
            if (sum < 0)
                sum = 0;
            result = max(result, sum);
        }
    }

    cout << result << endl;
}

void solve()
{
    input();
    simulate();
}
int main()
{   
    solve();
    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'void simulate()':
bulldozer.cpp:101:18: warning: variable 'slope' set but not used [-Wunused-but-set-variable]
  101 |         Fraction slope = event.first;
      |                  ^~~~~

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