Submission #1118161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118161		Pannda	Bulldozer (JOI17_bulldozer)	C++17	5 / 100	42 ms	592 KiB

bulldozer

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <ctime>
#include <cassert>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <array>
#include <bitset>
#include <sstream>
#include <unordered_map>
using ll = long long;
#define debug(x) cout << #x << " = " << x << '\n'
#define separator "===============================================\n"
#define all(a) a.begin(), a.end()
#define SZ(a) ((int)(a).size())
using namespace std;
const int mxn = 2e3 + 3;
const ll  mod = 1e9 + 7;
const int inf32 = 2e9;
const ll  inf64 = 7e18;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
struct point {
    ll x, y, w;
};
using Line = tuple<int, int, int>; // ax + by + c = 0
ll S(point a, point b, point c){
    return (b.x-a.x)*(b.y+a.y) + (c.x-b.x)*(c.y+b.y) + (a.x-c.x)*(a.y+c.y);
}
// determine which side point a is to line bc
bool cw(point a, point b, point c){
    ll d = S(a, b, c);
    return d > 0; // true = clockwise
}
Line get_line(point a, point b){
    return make_tuple(a.y - b.y, b.x - a.x, a.x * b.y - a.y * b.x);
}
long double dist(point A, Line d){
    ll a, b, c; tie(a, b, c) = d;
    ll num = a * A.x + b * A.y + c;
    ll denom = a * a + b * b;
    return 1.0 * num * num / denom;
}
int n;
point a[mxn];
void sub2(){
    ll res = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = i + 1; j <= n; ++j){
            vector<point> L, R;
            for (int k = 1; k <= n; ++k){
                if (k == i || k == j) continue;
                if (cw(a[k], a[i], a[j])) L.push_back(a[k]);
                else R.push_back(a[k]);
            }
            Line d = get_line(a[i], a[j]);
            sort(all(L), [&](point a, point b){
                return dist(a, d) < dist(b, d);
            });
            sort(all(R), [&](point a, point b){
                return dist(a, d) < dist(b, d);
            });
            // tilt the line slightly to adjust
            ll ini = max({0ll, a[i].w, a[j].w, a[i].w + a[j].w});
            res = max(res, ini);
            ll s = 0;
            for (point p : L){
                s += p.w;
                res = max(res, ini + s);
            }
            s = 0;
            for (point p : R){
                s += p.w;
                res = max(res, ini + s);
            }
        }
    }
    cout << res << '\n';
}
void solve(){
    cin >> n;
    bool flag_sub1 = true;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].x >> a[i].y >> a[i].w;
        flag_sub1 &= a[i].y == 0;
    }
    if (flag_sub1){
        ll res = 0;
        sort(a + 1, a + n + 1, [](point a, point b){
            return a.x < b.x;
        });
        for (int i = 1; i <= n; ++i){
            ll cur = 0;
            for (int j = i; j <= n; ++j){
                cur += a[j].w;
                res = max(res, cur);
            }
        }
        cout << res << '\n';
        return;
    }
    sub2();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    clock_t tStart = clock();
    int t = 1;
    // cin >> t;
    while(t--) solve();
    fprintf(stderr,"\n>> Runtime: %.10fs\n",(double)(clock()-tStart)/CLOCKS_PER_SEC);
}

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