Submission #947898

#	Time	Username	Problem	Language	Result	Execution time	Memory
947898		ha819ha	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	1 ms	860 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;

#define x first
#define y second
#define all(v) (v).begin(), (v).end()
#define vints(v, n) vint v(n); for(int& i:v) cin>>i;
#define vlls(v, n) vll v(n); for(ll& i:v) cin>>i;

const int sz = 2020;
struct Seg {
    ll dat[sz*2], sf[sz*2], pf[sz*2], mx[sz*2];

    void update(int x, ll v) {
        dat[x+=sz] = v;
        mx[x]=max(0LL, dat[x]);
        pf[x]=sf[x]=mx[x];
        for(x/=2;x;x/=2) {
            pf[x] = max(pf[2*x], dat[2*x]+pf[2*x+1]);
            sf[x] = max(sf[2*x+1], dat[2*x+1]+sf[2*x]);
            mx[x] = max({mx[2*x],mx[2*x+1], sf[2*x]+pf[2*x+1]});
            dat[x] = dat[2*x]+dat[2*x+1];
        }
    }
    ll get() {
        return mx[1];
    }
} S;

struct Point {
    ll x,y,v;

    bool operator < (const Point& rhs) const {
        return pll(x, y) < pll(rhs.x, rhs.y);
    }
};

struct Line {
    ll dx,dy,i,j;

    bool operator < (const Line& rhs) const {
        ll l = dy*rhs.dx, r = dx*rhs.dy;
        return tie(l, i, j) < tie(r, rhs.i, rhs.j);
    }

    bool operator == (const Line& rhs) const { 
        return dy*rhs.dx == dx*rhs.dy;
    }
};

int main(void){
    cin.tie(0)->sync_with_stdio(0);

    int n; cin>>n;
    vector<Point> p(n);
    for(auto& [x,y,v]:p) cin>>x>>y>>v;

    sort(all(p));
    vint pos(n); iota(all(pos), 0);

    vector<Line> lines;

    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            lines.push_back({
                p[j].x-p[i].x,
                p[j].y-p[i].y,
                i,j
            });
        }
    }
    sort(all(lines));

    for(int i=0;i<n;i++) {
        S.update(i, p[i].v);
    }

    ll ans = S.get();

    for(int a,b,i=0;i<lines.size();i++) {
        a = lines[i].i, b = lines[i].j;
        swap(p[pos[a]], p[pos[b]]);
        swap(pos[a], pos[b]);

        S.update(pos[a], p[pos[a]].v);
        S.update(pos[b], p[pos[b]].v);

        if(i+1<lines.size() && lines[i+1] == lines[i]) continue;

        ans = max(ans, S.get());
    }
    cout<<ans;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int a,b,i=0;i<lines.size();i++) {
      |                     ~^~~~~~~~~~~~~
bulldozer.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         if(i+1<lines.size() && lines[i+1] == lines[i]) continue;
      |            ~~~^~~~~~~~~~~~~

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