Submission #1197966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197966		Zero_OP	Bulldozer (JOI17_bulldozer)	C++20	5 / 100	85 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

#define dbg(x) "[" #x " = " << (x) << "]"

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){
            assert(_b != 0);
//            cout << _a << ' ' << _b << '\n';
            ll d = __gcd(abs(_a), abs(_b));
            _a /= d; _b /= d;
            if(_a < 0) _a = -_a, _b = -_b;
            a = _a; b = _b;
//            cout << "final : " << a << ' ' << b << '\n';
      }

      void refine(){
            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 {
            int cnt = (f.b < 0) ^ (b < 0);
            return (cnt ? a * f.b > f.a * b : a * f.b < f.a * b);
      }

      friend ostream& operator << (ostream& out, const Fraction& o){
            return out << '{' << o.a << ',' << o.b << '}';
      }
};

template<typename T>
ll max_subarray_sum(vector<pair<T, ll>>& v){
      sort(all(v));
      ll best = 0, pref = 0, min_pref = 0;
      for(int i = 0; i < sz(v); ++i){
            pref += v[i].ss;
            while(i+1 < sz(v) && v[i].ff == v[i+1].ff){
                  ++i;
                  pref += v[i].ss;
            }

            maximize(best, pref - min_pref);
            minimize(min_pref, pref);
      }
      return best;
}

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

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

      int N;
      cin >> N;
      vector<point> points(N);
      vi 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);
//                  cout << i << ' ' << j << " : " << frac.a << ' ' << frac.b << '\n';
                  slopes.eb(frac);
            }
      }

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

//      for(int i = 0; i < sz(slopes); ++i){
//            cout << "[" << slopes[i].a << ", " << slopes[i].b << "]\n";
//      }

      ll ans = 0;

      {
            vector<pair<int, ll>> ar;
            for(int i = 0; i < N; ++i) ar.eb(points[i].x, c[i]);
            maximize(ans, max_subarray_sum(ar));
      }

      {
            vector<pair<int, ll>> ar;
            for(int i = 0; i < N; ++i) ar.eb(points[i].y, c[i]);
            maximize(ans, max_subarray_sum(ar));
      }

//      cout << dbg(ans) << '\n';

      for(int _ = 0; _ < sz(slopes); ++_){
            Fraction f = slopes[_];
//            cout << '(' << f.a << ' ' << f.b << ')' << '\n';
            swap(f.a, f.b);
            f.b = -f.b;
            f.refine();

//            cout << dbg(f.a) << dbg(f.b) << '\n';

            vector<pair<Fraction, ll>> ar;
            for(int i = 0; i < N; ++i){
//                  cout << dbg(points[i]) << '\n';
//                  cout << points[i].y * f.b << ' ' << points[i].x * f.a << ' ' << f.b << '\n';
                  ar.eb(Fraction(points[i].y * f.b - points[i].x * f.a, f.b), c[i]);
//                  cout << ar.back().ff << '\n';
            }

            maximize(ans, max_subarray_sum(ar));
      }
      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