Submission #1197941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197941		Zero_OP	Bulldozer (JOI17_bulldozer)	C++20	5 / 100	19 ms	584 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ull = unsigned long long;
using ld = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vpl = vector<pl>;

using vvi = vector<vl>;
using vvl = vector<vl>;

struct point{
      ll x, y;
      point(ll _x = 0, ll _y = 0) : x(_x), y(_y) {}

      point& operator += (const point& a){
            x += a.x; y += a.y;
            return *this;
      }

      point& operator -= (const point& a){
            x -= a.x; y -= a.y;
            return *this;
      }

      friend point operator + (point a, const point& b){
            return a += b;
      }

      friend point operator - (point a, const point& b){
            return a -= b;
      }

      friend ostream& operator << (ostream& out, const point& p){
            return out << '(' << p.x << ',' << p.y << ')';
      }
};

ll cross2(const point& a, const point& b){
      return a.x * b.y - a.y * b.x;
}

ll cross3(const point& a, point b, point c){
      return cross2(b -= a, c -= a);
}

ll dot2(const point& a, const point& b){
      return a.x * b.x + a.y * b.y;
}

ll dot3(const point& a, point b, point c){
      return dot2(b -= a, c -= a);
}

struct Fraction{
      ll a, b;
      Fraction(ll a, ll b) : a(a), b(b) {
            assert(b != 0);
            ll d = __gcd(abs(a), abs(b));
            a /= d; b /= d;
            if(a < 0) a = -a, b = -b;
      }

      friend bool operator == (const Fraction& a, const Fraction& b){ return a.a == b.a && a.b == b.b; }
      friend bool operator != (const Fraction& a, const Fraction& b){ return !(a == b); }

      bool operator < (const Fraction& f) const {
            return a * f.b < f.a * b;
      }
};

int main(){
      ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
      freopen("task.inp", "r", stdin);
#endif //LOCAL

      int N;
      cin >> N;
      vector<point> points(N);
      vector<int> c(N);

      for(int i = 0; i < N; ++i){
            cin >> points[i].x >> points[i].y >> c[i];
      }

      vector<Fraction> slopes;
      for(int i = 0; i < N; ++i){
            for(int j = i+1; j < N; ++j){
                  if(points[i].x == points[j].x || points[i].y == points[j].y) continue;
                  Fraction frac(points[j].y - points[i].y, points[j].x - points[i].x);
                  slopes.eb(frac);
            }
      }

      sort(all(slopes));
      compact(slopes);

      ll ans = 0;

      {
            vpi ar;
            for(int i = 0; i < N; ++i) ar.eb(points[i].x, c[i]);
            sort(all(ar));
            bool ok = true;
            for(int i = 1; i+1 < N; ++i){
                  if(ar[i].ff == ar[i-1].ff && ar[i].ff == ar[i+1].ff){
                        ok = false;
                        break;
                  }
            }

            if(ok){
                  ll pref = 0, min_pref = 0;
                  for(int i = 0; i < N; ++i){
                        pref += ar[i].ss;
                        maximize(ans, pref - min_pref);
                        minimize(min_pref, pref);
                  }
            }
      }

      {
            vpi ar;
            for(int i = 0; i < N; ++i) ar.eb(points[i].y, c[i]);
            sort(all(ar));

            bool ok = true;
            for(int i = 1; i+1 < N; ++i){
                  if(ar[i].ff == ar[i-1].ff && ar[i].ff == ar[i+1].ff){
                        ok = false;
                        break;
                  }
            }

            if(ok){
                  ll pref = 0, min_pref = 0;
                  for(int i = 0; i < N; ++i){
                        pref += ar[i].ss;
                        maximize(ans, pref - min_pref);
                        minimize(min_pref, pref);
                  }
            }
      }

      for(int _ = 0; _ < sz(slopes); ++_){
            Fraction f = slopes[_];
            swap(f.a, f.b);

            vector<pair<Fraction, int>> ar;
            for(int i = 0; i < N; ++i){
                  ar.eb(Fraction(points[i].y * f.b - points[i].x * f.a, f.b), c[i]);
            }

            sort(all(ar));
            ll pref = 0, min_pref = 0;
            for(int i = 0; i < N; ++i){
                  pref += ar[i].ss;
                  maximize(ans, pref - min_pref);
                  minimize(min_pref, pref);
            }
      }
      cout << ans << '\n';

      return 0;
}

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