Submission #338573

#	Time	Username	Problem	Language	Result	Execution time	Memory
338573		theshadow_04	Bulldozer (JOI17_bulldozer)	C++14	5 / 100	65 ms	492 KiB

bulldozer

// V T An
#include <bits/stdc++.h>
#define Task "BULLDOZER"
#define F first
#define S second

using namespace std;

const int maxn = 2005;

int n;
struct data {
    long long x, y, w;

    bool operator < (const data A) {
        return x < A.x;
    }
} point[maxn];

namespace Sub1 {

    long long s[maxn], ans = 0;

    void Solve() {
        sort(point + 1, point + n + 1);
        for(int i = 1; i <= n; ++ i) {
            s[i] = s[i - 1] + point[i].w;
        }
        for(int i = 1; i <= n; ++ i) {
            for(int j = i; j <= n; ++ j) {
                ans = max(ans, s[j] - s[i - 1]);
            }
        }
        cout << ans << "\n";
    }
}

namespace Sub2 {

    long long A, B, C;
    int cnt = 0;
    long long cur[maxn];

    long long DistoLine(long long a, long long b, long long c, long long x, long long y) {
        return a * x + b * y + c;
    }

    bool comp(data p, data q) {
        return DistoLine(A, B, C, p.x, p.y) < DistoLine(A, B, C, q.x, q.y);
    }

    void Solve() {
        long long ans = 0;
        for(int i = 1; i <= n; ++ i) {
            pair<long long, long long> c = {point[i].x, point[i].y};
            ans = max(ans, point[i].w);
            for(int j = i + 1; j <= n; ++ j) {
                pair<long long, long long> d = {point[j].x, point[j].y};
                pair<long long, long long> u = {d.F - c.F, d.S - c.S};
                A = u.S, B = -u.F, C = - (A * c.F + B * c.S);
                cnt = 0;
                sort(point + 1, point + n + 1, comp);
                for(int k = 1; k <= n; ++ k) {
                    if(k && DistoLine(A, B, C, point[k].x, point[k].y) == DistoLine(A, B, C, point[k - 1].x, point[k - 1].y)){
                        cur[cnt] += point[k].w;
                    } else cur[++ cnt] = point[k].w;
                }
                for(int k = 1; k <= cnt; ++ k) cur[k] += cur[k - 1];
                for(int p = 1; p <= cnt; ++ p)
                    for(int q = p; q <= cnt; ++ q)
                        ans = max(ans, cur[q] - cur[p - 1]);
            }
        }
        cout << ans;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
	if(fopen(Task".inp", "r")){
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}
    cin >> n;
    int sub1 = 1;
    for(int i = 1; i <= n; ++ i) {
        int x, y, w;
        cin >> x >> y >> w;
        point[i] = {x, y, w};
        if(y) sub1 = 0;
    }
    if(sub1) {
        Sub1::Solve();
        return 0;
    }
    Sub2::Solve();
}

// CHY-AKAV

Compilation message (stderr)

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

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