Submission #338611

#	Time	Username	Problem	Language	Result	Execution time	Memory
338611		KazamaHoang	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	20 ms	364 KiB

bulldozer

/* -> Written by <-
   -----------
  K_A_Z_A_M_A
  ___________
      _    |
  |   (^_^)   |
  |  /( | )\  |
  |____|_|____|
    H O A N G
*/

#include <bits/stdc++.h>

#define Task            "bulldozer"
#define F               first
#define S               second
#define pb              push_back
#define bit(x, i)       ((x >> (i)) & 1)

#define inf             1e9 + 7
#define INF             1e18 + 7
#define ll              long long
#define pii             pair <int, int>
#define debug(x)        cerr << #x << " is " << x << "\n";

using namespace std;

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;

int n;
pair <pii, int> a[maxn];

struct LINE{
    ll A, B, C;
};

pii Vt(pair<pii, int> p, pair<pii, int> q){
    return {q.F.F - p.F.F, q.F.S - p.F.S};
}

LINE Make_Line(pair<pii, int> p, pair<pii, int> q){
    pii u = Vt(p, q);
    LINE c;
    c.A = u.S;
    c.B = - u.F;
    c.C = 1ll * p.F.S * u.F - 1ll * p.F.F * u.S;
    return c;
}

ll dis(pair<pii, int> p, LINE c){
    return abs(c.A * p.F.F + c.B * p.F.S + c.C);
}

pair <ll, int> b[maxn], v[maxn];

ll Cal(pair<ll, int> t[], int cnt){
    sort(t + 1, t + 1 + cnt);
    ll s = 0;
    ll res = 0;
    for (int i = 1; i <= cnt; ++ i){
        s += a[t[i].S].S;
        res = max(res, s);
    }
    return res;
}

void Solve(){
    cin >> n;
    for (int i = 1; i <= n; ++ i){
        cin >> a[i].F.F >> a[i].F.S >> a[i].S;
    }
    ll res = 0;
    for (int i = 1; i <= n; ++ i){
        res = max(res, (ll)a[i].S);
        for (int j = i + 1; j <= n; ++ j){
            int cnt = 0, dem = 0;
            LINE c = Make_Line(a[i], a[j]);
            for (int h = 1; h <= n; ++ h){
                if (h != i && h != j){
                    ll sd = c.A * a[h].F.F + c.B * a[h].F.S + c.C;
                    if (sd > 0) b[++cnt] = {dis(a[h], c), h};
                    else v[++dem] = {dis(a[h], c), h};
                }
            }
            res = max(res, Cal(b, cnt));
            res = max(res, Cal(v, dem));
        }
    }
    cout << res;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if(fopen(Task".inp", "r")){
        freopen(Task".inp","r",stdin);
        freopen(Task".out","w",stdout);
    }
    int test_case = 1;
//     cin >> test_case;
    while (test_case --){
        Solve();
    }

    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   96 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bulldozer.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   97 |         freopen(Task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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