Submission #1110051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110051		vladilius	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	3 ms	860 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct ST{
    struct node{
        ll pr, sf, mx, s;
    };
    vector<node> t;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
    }
    void upd(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            t[v].s = x;
            t[v].pr = t[v].sf = t[v].mx = max(0, x);
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, x);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x);
        }
        t[v].s = t[vv].s + t[vv + 1].s;
        t[v].mx = max({t[vv].mx, t[vv + 1].mx, t[vv].sf + t[vv + 1].pr});
        t[v].pr = max(t[vv].pr, t[vv].s + t[vv + 1].pr);
        t[v].sf = max(t[vv + 1].sf, t[vv + 1].s + t[vv].sf);
    }
    void upd(int p, int x){
        upd(1, 1, n, p, x);
    }
    ll get(){
        return t[1].mx;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> x(n + 1), y(n + 1), a(n + 1), f;
    for (int i = 1; i <= n; i++){
        cin>>x[i]>>y[i]>>a[i];
        f.pb(i);
    }
    
    auto cmp = [&](int i, int j){
        return x[i] < x[j];
    };
    sort(f.begin(), f.end(), cmp);
    vector<int> p(n + 1);
    for (int i = 0; i < n; i++){
        p[f[i]] = i + 1;
    }
    ST T(n);
    for (int i = 1; i <= n; i++){
        T.upd(p[i], a[i]);
    }
    
    ll out = 0;
    int i = 0;
    ll sum = 0;
    while (i < n){
        int j = i; ll s = 0;
        while (j < n && x[f[i]] == x[f[j]]){
            s += a[f[j]];
            j++;
        }
        sum += s;
        sum = max(sum, 0LL);
        out = max(out, sum);
        i = j;
    }
    
    vector<pair<ld, pii>> all;
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            if (x[i] != x[j]){
                ld d = 1.0 * (y[i] - y[j]) / (x[i] - x[j]);
                all.pb({d, {i, j}});
            }
        }
    }
    sort(all.begin(), all.end());
    
    for (auto pp: all){
        auto [u, v] = pp.ss;
        
        T.upd(p[u], a[u] + a[v]);
        T.upd(p[v], 0);
        
        out = max(out, T.get());
        
        swap(p[u], p[v]);
        T.upd(p[u], a[u]);
        T.upd(p[v], a[v]);
    }
    
    cout<<out<<"\n";
}

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