제출 #1110139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110139		vladilius	Bulldozer (JOI17_bulldozer)	C++17	5 / 100	2 ms	688 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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 = {0};
    for (int i = 1; i <= n; i++){
        cin>>x[i]>>y[i]>>a[i];
        f.pb(i);
    }
    
    auto cmp = [&](int i, int j){
        if (x[i] == x[j]){
            return y[i] < y[j];
        }
        return x[i] < x[j];
    };
    sort(f.begin() + 1, f.end(), cmp);
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++){
        p[f[i]] = i;
    }
    ST T(n);
    for (int i = 1; i <= n; i++){
        T.upd(p[i], a[i]);
    }
    ll out = T.get();
    
    vector<pair<pii, pii>> all;
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            if (x[f[i]] != x[f[j]]){
                all.pb({{y[f[j]] - y[f[i]], x[f[j]] - x[f[i]]}, {f[i], f[j]}});
            }
        }
    }
    
    auto cmp1 = [&](pair<pii, pii> a, pair<pii, pii> b){
        auto [u1, v1] = a.ff;
        auto [u2, v2] = b.ff;
        return 1LL * u1 * v2 < 1LL * u2 * v1;
    };
    
    sort(all.begin(), all.end(), cmp1);
    vector<bool> used(n + 1);
    vector<int> ff, pp;
    int i = 0;
    while (i < all.size()){
        int j = i;
        while (j < all.size() && (1LL * all[i].ff.ff * all[j].ff.ss) == (1LL * all[i].ff.ss * all[j].ff.ff)){
            j++;
        }
        
        ll r, q;
        if (j == all.size()){
            r = 2e9 + 1;
            q = 1;
        }
        else {
            r = all[i].ff.ff + all[j].ff.ff;
            q = all[i].ff.ss + all[j].ff.ss;
        }
        auto cmp2 = [&](int u, int v){
            if (x[u] == x[v]) return y[u] < y[v];
            return q * (y[u] - y[v]) < r * (x[u] - x[v]);
        };
        
        ff.clear(); pp.clear();
        for (int k = i; k < j; k++){
            auto [u, v] = all[k].ss;
            if (!used[u]){
                used[u] = 1;
                ff.pb(u);
                pp.pb(p[u]);
            }
            if (!used[v]){
                used[v] = 1;
                ff.pb(v);
                pp.pb(p[v]);
            }
        }
        sort(ff.begin(), ff.end(), cmp2);
        sort(pp.begin(), pp.end());
        for (int i = 0; i < pp.size(); i++){
            p[ff[i]] = pp[i];
            T.upd(pp[i], a[ff[i]]);
        }
        for (int k = i; k < j; k++){
            auto [u, v] = all[k].ss;
            used[u] = used[v] = 0;
        }
        
        out = max(out, T.get());
        i = j;
    }
    
    cout<<out<<"\n";
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:93:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     while (i < all.size()){
      |            ~~^~~~~~~~~~~~
bulldozer.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         while (j < all.size() && (1LL * all[i].ff.ff * all[j].ff.ss) == (1LL * all[i].ff.ss * all[j].ff.ff)){
      |                ~~^~~~~~~~~~~~
bulldozer.cpp:100:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         if (j == all.size()){
      |             ~~^~~~~~~~~~~~~
bulldozer.cpp:129:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int i = 0; i < pp.size(); i++){
      |                         ~~^~~~~~~~~~~

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