Submission #891229

#	Time	Username	Problem	Language	Result	Execution time	Memory
891229		Zanite	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	996 ms	81076 KiB

bulldozer

// When we're in drama,
// there's that person over there
// polishing their skill.

// 抗えぬ運命と決まっているのなら
// 私はあなたの為に生きたい
// 誰かの為に生きてこその人生
// 輝を増すこと知っているから

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// Pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
using namespace std;
using namespace __gnu_pbds;

// Data types
using si  = short int;
using ll  = long long;
using ull = unsigned long long;
using lll = __int128;
using ld  = long double;

// Pairs
using pii  = pair<int, int>;
using psi  = pair<si, si>;
using pll  = pair<ll, ll>;
using plll = pair<lll, lll>;
using pld  = pair<ld, ld>;
#define fi first
#define se second

// PBDS
template<typename Z>
using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;

// Various outputs
template<typename Y, typename Z>
ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
    return os << "(" << p.fi << ", " << p.se << ")";
}
template<typename RZ>
ostream& operator<<(ostream &os, const tuple<RZ, RZ> &r) {
    os << "{"; bool _first = 1;
    for (RZ i = get<0>(r); i != get<1>(r); i++) {
        if (!_first) os << ", ";
        os << *i; _first = 0;
    }
    return os << "}";
}
template<typename Z>
ostream& operator<<(ostream &os, const vector<Z> &v) {
    return os << make_tuple(v.begin(), v.end());
}

// Quick macro functions
#define sqr(x)        ((x)*(x))
#define debug(x)      cout << #x << " = " << (x) << '\n'
#define debugV(v, x)  cout << #v << "[" << (x) << "] = " << (v[x]) << '\n'
#define rrebug(x)     cerr << #x << " = " << (x) << '\n'
#define rrebugV(v, x) cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n'

#define All(x)       x.begin(), x.end()
#define Sort(x)      sort(All(x))
#define Reverse(x)   reverse(All(x))
#define Uniqueify(x) Sort(x); x.erase(unique(All(x)), x.end())

#define RandomSeed        chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)

// Check min and max
template<typename Z> bool chmin(Z &a, Z b) {return (b < a) ? a = b, true : false;}
template<typename Z> bool chmax(Z &a, Z b) {return (b > a) ? a = b, true : false;}
 
// Modular arithmetic
template<int MOD>
class ModInt {
  public:
    int v;
    ModInt() : v(0) {}
    ModInt(long long _v) {
        v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
        if (v < 0) v += MOD;
    }
 
    friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;}
    friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;}
    friend bool operator< (const ModInt &a, const ModInt &b) {return a.v <  b.v;}
    friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;}
    friend bool operator> (const ModInt &a, const ModInt &b) {return a.v >  b.v;}
    friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;}
 
    ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;}
    ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;}
    ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;}
    ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);}
 
    friend ModInt pow(ModInt a, long long x) {
        ModInt res = 1;
        for (; x; x /= 2, a *= a) if (x & 1) res *= a;
        return res;
    }
    friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);}
 
    ModInt operator+ () const {return ModInt( v);}
    ModInt operator- () const {return ModInt(-v);}
    ModInt operator++() const {return *this += 1;}
    ModInt operator--() const {return *this -= 1;}
 
    friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;}
    friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;}
    friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;}
    friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;}
 
    friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;}
    friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;}
};
const int ModA = 998244353;
const int ModC = 1e9 + 7;
using MintA    = ModInt<ModA>;
using MintC    = ModInt<ModC>;

// Other constants
const ll INF  = 1e18;
const ll iINF = 1e9;
const ld EPS  = 1e-9;
const ld iEPS = 1e-6;

template<typename Z>
bool geomAbs(Z x) {
    if (x < EPS) return x;
    return x;
}
template<typename Z>
bool geomBetween(Z x, Z l, Z r) {
    // l <= x <= r
    if (l > r) swap(l, r);
    return (l <= x + EPS) && (x <= r + EPS);
}
template<typename Z>
bool geomEqual(Z a, Z b) {
    return geomBetween(a, b, b);
}

// Point

template<typename Z>
struct Point {
    Z x, y;
    
    Point(Z x = 0, Z y = 0) :
        x(x), y(y)
    {}

    bool operator<(const Point<Z> &other) const {
        if (x < other.x + EPS) return true;
        if (x + EPS > other.x) return false;
        return y < other.y + EPS;
    }
    bool operator==(const Point &other) const {
        return geomEqual(x, other.x) && geomEqual(y, other.y);
    }

    friend istream& operator>>(istream &is, Point<Z> &P) {
        return is >> P.x >> P.y;
    }
};

template<typename Z>
struct Line {
    Z a, b, c;

    Line(Z a = 0, Z b = 0, Z c = 0) :
        a(a), b(b), c(c)
    {}
    Line(Point<Z> P1, Point<Z> P2) {
        if (P1 < P2) swap(P1, P2);
        if (geomEqual(P1.x, P2.x)) {
            a = 1;
            b = 0;
            c = -P1.x;
        } else {
            a = -(P1.y - P2.y) / (P1.x - P2.x);
            b = 1;
            c = -(a * P1.x) - P1.y;
        }
    }
    Line(Point<Z> P, Z slope) {
        a = -slope;
        b = 1;
        c = -(a * P.x) - P.y;
    }

    bool operator==(const Line &other) const {
        return geomEqual(a, other.a) && geomEqual(b, other.b) && geomEqual(c, other.c);
    }

    ld slope() {
        return -((ld)a / (ld)b);
    }
};

struct Segtree {
    struct Elm {
        ll pf, sf, mx, sum;
        Elm() {
            pf = sf = mx = -INF;
            sum = 0;
        }
        Elm(ll val) {
            pf = sf = mx = max(val, 0ll);
            sum = val;
        }
    };
	Elm DEFAULT = Elm();

	#define m	((l+r) >> 1)
	#define lc	(pos << 1)
	#define rc	(lc | 1)

	int sz;
	vector<Elm> seg;

	Segtree(int sz) : sz(sz) {seg.assign((sz << 2) + 1, DEFAULT);}

	void updateNode(int pos, ll val) {
		seg[pos] = Elm(val);
	}

	Elm merge(Elm a, Elm b) {
		Elm nw = Elm();
        nw.pf = max({-INF, a.pf, a.sum + b.pf});
        nw.sf = max({-INF, b.sf, b.sum + a.sf});
        nw.mx = max({-INF, a.mx, b.mx, a.sf + b.pf});
        nw.sum = a.sum + b.sum;
        return nw;
	}

	void update(int pos, int l, int r, int idx, ll val) {
		if (l == r) {
			updateNode(pos, val);
			return;
		}

		if (idx <= m) {update(lc, l, m, idx, val);}
		else {update(rc, m+1, r, idx, val);}
		seg[pos] = merge(seg[lc], seg[rc]);
	}
	void update(int idx, ll val) {update(1, 1, sz, idx, val);}

	Elm query(int pos, int l, int r, int ql, int qr) {
		if (l > r || ql > qr || ql > r || l > qr) {return DEFAULT;}
		if (ql <= l && r <= qr) {return seg[pos];}

		return merge(query(lc, l, m, ql, qr), query(rc, m+1, r, ql, qr));
	}
	Elm query(int ql, int qr) {return query(1, 1, sz, ql, qr);}

	#undef	m
	#undef	lc
	#undef	rc
};

bool _less(ld x, ld y) {return x - y < -EPS;}
bool _greater(ld x, ld y) {return x - y > EPS;}

using TempPoint = tuple<ll, ll, ll>; // {x, y, w}
const ld ld_infinity = (ld)1 / (ld)0;

const int maxN  = 2'023;

int N;
TempPoint TP[maxN];
pll P[maxN];
ll W[maxN];
ld C[maxN][maxN];
vector<pii> pairs;
int pos[maxN];

ld getLineC(pll a, pll b) {
    if (a.fi == b.fi) {
        return -a.fi;
    } else {
        ld d = -(ld)(a.se - b.se) / (ld)(a.fi - b.fi);
        ld c = -d * (ld)(a.fi) - (ld)a.se;
        return c;
    }
}

int compareSlope(pii a, pii b) {
    pll A1 = P[a.fi], A2 = P[a.se];
    pll B1 = P[b.fi], B2 = P[b.se];

    bool a_inf = (A1.fi == A2.fi);
    bool b_inf = (B1.fi == B2.fi);
    if (a_inf && b_inf) return 0;
    if (a_inf) return -1;
    if (b_inf) return 1;

    //    (A2.y - A1.y) / (A1.x - A2.x) - (B2.y - B1.y) / (B1.x - B2.x)
    // -> (A2.y - A1.y)(B1.x - B2.x) - (B2.y - B1.y)(A1.x - A2.x)

    ll cur = (A2.se - A1.se) * (B1.fi - B2.fi) - (B2.se - B1.se) * (A1.fi - A2.fi);
    if (cur < 0) return -1;
    if (cur > 0) return 1;
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> N;
    for (int i = 1; i <= N; i++) {
        auto &[x, y, w] = TP[i];
        cin >> x >> y >> w;
    }

    sort(TP + 1, TP + N + 1);
    for (int i = 1; i <= N; i++) {
        auto &[x, y, w] = TP[i];
        P[i] = {x, y};
        W[i] = w;
    }

    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            C[i][j] = getLineC(P[i], P[j]);
            pairs.push_back({i, j});
        }
    }

    sort(All(pairs), [&](const pii &a, const pii &b){
        auto &[ai, aj] = a;
        auto &[bi, bj] = b;

        int cs = compareSlope(a, b);
        if (cs == -1) return true;
        if (cs == 1) return false;

        if (_less(C[ai][aj], C[bi][bj])) return true;
        if (_greater(C[ai][aj], C[bi][bj])) return false;

        if (ai < bi) return true;
        if (ai > bi) return false;
        return aj < bj;
    });

    Segtree S(N);
    for (int i = 1; i <= N; i++) {
        pos[i] = i;
        S.update(i, W[i]);
    }
    ll ans = S.query(1, N).mx;
    int P = pairs.size();

    for (int i = 0; i < P; i++) {
        auto &[ci, cj] = pairs[i];
        swap(pos[ci], pos[cj]);
        S.update(pos[ci], W[ci]);
        S.update(pos[cj], W[cj]);

        bool process = true;
        if (i < P-1) {
            if (compareSlope(pairs[i], pairs[i+1]) != -1) {
                process = false;
            }
        }

        if (process) {
            chmax(ans, S.query(1, N).mx);
        }
    }

    cout << ans << "\n";
}

// あなたの傍に居させて...

// dibisakan

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