제출 #1198016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198016		Zero_OP	Bulldozer (JOI17_bulldozer)	C++20	5 / 100	17 ms	328 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{
      int x, y, c;
};

template<typename T>
ll max_subarray_sum(vector<pair<T, int>>& v){
      sort(all(v));
//      for(int i = 0; i < sz(v); ++i) cout << fixed << setprecision(4) << v[i].ff << " \n"[i == sz(v)-1];
//      for(int i = 0; i < sz(v); ++i) cout << v[i].ss << " \n"[i == sz(v)-1];
      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);
      }
//      cout << dbg(best) << '\n';
      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);

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

      ll ans = 0;
      vpi arx, ary;
      for(int i = 0; i < N; ++i){
            maximize(ans, (ll)points[i].c);
            arx.eb(points[i].x, points[i].c);
            ary.eb(points[i].y, points[i].c);
      }

      maximize(ans, max_subarray_sum(arx));
      maximize(ans, max_subarray_sum(ary));

      for(int i = 0; i < N; ++i){
            for(int j = i+1; j < N; ++j){
                  ll a = points[i].y - points[j].y;
                  ll b = points[j].x - points[i].x;
                  if(a == 0 || b == 0) continue;
//                  cout << dbg(i) << dbg(j) << dbg(a) << dbg(b) << '\n';
                  ll d = __gcd(abs(a), abs(b));
                  a /= d; b /= d;
                  if(b < 0) a = -a, b = -b;
                  //ax + by

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

                  maximize(ans, max_subarray_sum(ar));
//                  cout << '\n';
            }
      }

      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