Submission #338511

# Submission time Handle Problem Language Result Execution time Memory
338511 2020-12-23T10:00:21 Z theshadow_04 Bulldozer (JOI17_bulldozer) C++14
5 / 100
468 ms 364 KB
// 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 DistoLine(long long a, long long b, long long c, long long x, long long y) {
        return abs(a * x + b * y + c);
    }

    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};
            for(int j = 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};
                long long A = u.S, B = -u.F, C1 = - (A * c.F + B * c.S);
                for(int k = 1; k <= n; ++ k) if(k != j && k != i) {
                    long long C2 = - (A * point[k].x + B * point[k].y);
                    long long Dis = DistoLine(A, B, C1, point[k].x, point[k].y);
                    long long res = 0;
                    for(int p = 1; p <= n; ++ p) {
                        long long Dis1 = DistoLine(A, B, C1, point[p].x, point[p].y);
                        long long Dis2 = DistoLine(A, B, C2, point[p].x, point[p].y);
                        if(Dis == Dis1 + Dis2) res += point[p].w;
                    }
                    ans = max(ans, res);
                    res = 0;
                    for(int p = 1; p <= n; ++ p) {
                        long long Dis1 = DistoLine(A, B, C1, point[p].x, point[p].y);
                        long long Dis2 = DistoLine(A, B, C2, point[p].x, point[p].y);
                        if(Dis1 && Dis == Dis1 + Dis2) res += point[p].w;
                    }
                }
            }
        }
        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

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:79:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   freopen(Task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bulldozer.cpp:80:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   80 |   freopen(Task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 468 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 468 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 468 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Incorrect 468 ms 364 KB Output isn't correct
17 Halted 0 ms 0 KB -