Submission #551415

#	Time	Username	Problem	Language	Result	Execution time	Memory
551415		cadmiumsky	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	4 ms	468 KiB

bulldozer

#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
const int nmax = 1e3 + 5;
int n;

namespace SSM {
  //#define int ll
  struct Node {
    int sum, pref, suff, mx;
    Node() : sum(0), pref(0), suff(0), mx(0) {;}
    Node(int val) : sum(val), pref(max(0LL, val)), suff(max(0LL, val)), mx(max(0LL, val)) {;}
    Node(int s, int p, int u, int m) : sum(s), pref(p), suff(u), mx(m) {;}
    Node operator +(const Node& x) const {
      return Node(x.sum + sum, 
                  max(pref, sum + x.pref), 
                  max(x.suff, x.sum + suff), 
                  max({mx, x.mx, suff + x.pref}));
    }
  };
  //#undef int
  Node aint[nmax * 4];
  void upd(int poz, ll val, int node = 1, int cl = 0, int cr = n - 1) {
    if(cl == cr) {
      aint[node] = Node(val);
      return;
    }
    int mid = cl + cr >> 1;
    if(poz <= mid)
      upd(poz, val, 2 * node, cl, mid);
    else
      upd(poz, val, 2 * node + 1, mid + 1, cr);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
  ll query() { return aint[1].mx; }
};

vector< tuple<int,int,int> > points;
vector<int> ind;

namespace LineContainer { // catthink
  pair<int,int> getline(int l, int r) { return {-(get<1>(points[l]) - get<1>(points[r])), -(get<0>(points[l]) - get<0>(points[r]))};}; 
  auto cmpline = [](pair<int,int> l, pair<int,int> r) { 
    if(l.second == 0 && r.second == 0)
      return false;
    if(l.second == 0)
      return true;
    if(r.second == 0)
      return false;
    if(!((((ll)l.first * l.second) >= 0) ^ ((((ll)l.first * l.second) >= 0))))
      return (ll)l.first * r.second > (ll)r.first * l.second;
    return (ll)l.first * r.second < (ll)r.first * l.second;
  };
  auto eqline = [](pair<int,int> l, pair<int,int> r) { return !cmpline(l, r) && !cmpline(r, l); };
  auto eq = [](int i, int j) { return eqline(getline(ind[i], ind[i + 1]), getline(ind[j], ind[j + 1])); };
  auto cmp = [](int i, int j) { return cmpline(getline(ind[i], ind[i + 1]), getline(ind[j], ind[j + 1]))
                                        || (eq(i, j) && i < j); };
  set<int, decltype(cmp)> heap(cmp);
  void rev(int l, int r) {
    if(l > 0 && ind[l - 1] < ind[l])
      heap.erase(l - 1);
    if(r < ind.size() - 1 && ind[r] < ind[r + 1])
      heap.erase(r);
    reverse(ind.begin() + l, ind.begin() + r + 1);
    if(l > 0 && ind[l - 1] < ind[l])
      heap.insert(l - 1);
    if(r < ind.size() - 1 && ind[r] < ind[r + 1])
      heap.insert(r);
    for(int i = l; i <= r; i++) {
      SSM::upd(i, get<2>(points[ind[i]]));
    }    
  }
  int startmove() {
    if(heap.size() == 0)
      return -1;
    int u = *heap.begin(), last = u;
    //cerr << "- " << u << '\n';
    heap.erase(heap.begin());
    while(!heap.empty() && eq(*heap.begin(), u)) {
      if(*heap.begin() - u > 1) {
        rev(last, u + 1);
        last = *heap.begin();
      }
      u = *heap.begin();
      heap.erase(heap.begin());
    }
    rev(last, u + 1);
    return SSM::query();
  }
}

signed main() {
  cin >> n;
  points.resize(n);
  ind.resize(n);
  for(auto &[a, b, c] : points)
    cin >> a >> b >> c;
  sort(points.begin(), points.end());
  for(int i = 0; i < n; i++)
    //cerr << get<0>(points[i]) << ' ' << get<1>(points[i]) << '\n', 
    SSM::upd(i, get<2>(points[i])),
    ind[i] = i;
  for(int i = 0; i < n - 1; i++)
    LineContainer::heap.insert(i);
  int mx = SSM::query(), temp;
  while((temp = LineContainer::startmove()) >= 0) {
    //cerr << temp << '\n';
    mx = max(mx, temp);
  }
  cout << mx << '\n';
}

Compilation message (stderr)

bulldozer.cpp: In function 'void SSM::upd(long long int, ll, long long int, long long int, long long int)':
bulldozer.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
bulldozer.cpp: In function 'void LineContainer::rev(long long int, long long int)':
bulldozer.cpp:63:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if(r < ind.size() - 1 && ind[r] < ind[r + 1])
      |        ~~^~~~~~~~~~~~~~~~
bulldozer.cpp:68:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     if(r < ind.size() - 1 && ind[r] < ind[r + 1])
      |        ~~^~~~~~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:97:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |   for(auto &[a, b, c] : points)
      |             ^

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