Submission #1036704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036704		Misha_Yuzvik	Bulldozer (JOI17_bulldozer)	C++14	80 / 100	1006 ms	66416 KiB

bulldozer

# include <bits/stdc++.h>
using namespace std;
# define For(i , l , r) for(int i = (l); i <= (r); i++)
# define Rep(i , n) For(i , 0 , (n) - 1)
# define size(x) (long long)x.size()
# define MAXN 2000005
# define MAXK 1000005
# define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll inf = 1e9 + 7;
const ll mod = 1e9 + 9;
const ld eps = 0.000000001;
ll n , m , k , ans = 0 , q;
struct pt {
   ll x , y , val;
   bool operator == (const pt& p) {
       return (p.x == x && p.y == y);
   }
};
struct vc {
    ll x , y;
    ll nom1 , nom2;
};
ll cross_pr(const vc &a , const vc& b) {
  //  cout << a.x << ' ' << a.y << ' ' << b.x << ' ' << b.y << "\n";
    return a.x * b.y - b.x * a.y;
}
struct node {
    ll sum , wyn , mxp , mxs;
};
vector<node>t;
ll sz = 1;
void init(ll n) {
    while (sz < n) sz *= 2;
    t.resize(sz * 3 + 5);
}
node calc(node &left , node &right) {
     node cur = {0 , 0 , 0 , 0};
     cur.sum = left.sum + right.sum;
     cur.mxp = max(left.mxp , left.sum + right.mxp);
     cur.mxs = max(right.mxs , right.sum + left.mxs);
     cur.wyn = max({left.wyn , right.wyn , left.mxs + right.mxp});
     return cur;
}
void upd(ll nom , ll val , ll x , ll lx , ll rx) {
       if (rx - lx == 1) {
            t[x].sum = val;
            t[x].mxp = t[x].mxs = t[x].wyn = max(0LL , val);
            return;
       }
       ll mid = (lx + rx) / 2;
       if (nom < mid) upd(nom , val , (x << 1) , lx , mid);
       else upd(nom , val , (x << 1) + 1 , mid , rx);
       t[x] = calc(t[x << 1] , t[(x << 1) + 1]);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    vector<pt>p(n);
    for (auto &[x , y , val] : p) cin >> x >> y >> val;
    sort(p.begin() , p.end() , 
         [](const auto& l , const auto& r) {
             if (l.x == r.x) return l.y > r.y;
             return l.x < r.x;   
         });
    vector<vc>line;
    Rep (i , n) {
        For (j , i + 1 , n - 1) {
            line.push_back({p[i].x - p[j].x , p[i].y - p[j].y , i , j});  
            if (size(line) > 0 && line.back().x == 0) line.pop_back();
            if (size(line) > 0 && line.back().x < 0) line.back().x *= -1 , line.back().y *= -1;
        }
    }
    sort(all(line) , 
       [&](const vc& l , const vc& r) {
            //  cout << 0 << endl;
              ll f = cross_pr(l , r);
              if (f == 0) {
               //   cout << 1 << endl;
                  if (p[l.nom1] == p[r.nom1]) return p[l.nom2].x < p[r.nom2].x;
                  else return p[l.nom1].x < p[r.nom1].x;
              } 
              return f < 0;
    });
    init(n);
    Rep (i , n) {
        upd(i , p[i].val , 1 , 0 , sz);
    }
    vector<ll>pos(n);
    Rep (i , n) pos[i] = i;
    ans = t[1].wyn;
    if (size(line) == 0) {
        cout << ans;
        return 0;
    }
    ld prev_tg = (ld)line[0].y / (ld)line[0].x;
    Rep (i , size(line)) {
          ll x = line[i].x , y = line[i].y , nom1 = line[i].nom1 , nom2 = line[i].nom2;
          if ((ld)y / (ld)x != prev_tg) {
            ll cur_res = t[1].wyn;
            ans = max(ans , cur_res);
            prev_tg = (ld)y / (ld)x;
          }
          swap(pos[nom1] , pos[nom2]);
          ll pos1 = pos[nom1] , pos2 = pos[nom2];
          upd(pos1 , p[nom1].val , 1 , 0 , sz);
          upd(pos2 , p[nom2].val , 1 , 0 , sz);
          
    }
    ans = max(ans , t[1].wyn);
    cout << ans;
}
/*

*/

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:62:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for (auto &[x , y , val] : p) cin >> x >> y >> val;
      |                ^

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