oj.uz

Submission #1117780

# Submission time Handle Problem Language Result Execution time Memory
1117780 2024-11-24T08:18:57 Z Pannda Bulldozer (JOI17_bulldozer) C++17
0 / 100
 53 ms 764 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long double F;
typedef complex<F> point;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<point> a(n);
    vector<int> w(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y >> w[i];
        a[i] = point(x, y);
    }

    vector<F> thetas = [&] { // Gives a list of critical points in [-pi/2,pi/2) in order, expressed by (i, j) : before the critical point i<j and after that i>j. When exactly are the critical points are not returned
        vector<F> res;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (y0 != y1) {
                    F tan = (a[i].real() - a[j].real()) / (a[i].imag() - a[j].imag());
                    res.push_back(atan(tan));
                }
            }
        }
        sort(res.begin(), res.end());
        return res;
    }();

    long long ans = 0;
    for (F theta : thetas) {
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(), [&](int i, int j) -> bool {
            point x(cos(theta) * a[i].real() - sin(theta) * a[i].imag(), sin(theta) * a[i].real() + cos(theta) * a[i].imag());
            point y(cos(theta) * a[j].real() - sin(theta) * a[j].imag(), sin(theta) * a[j].real() + cos(theta) * a[j].imag());
            return x.real() < y.real();
        });
        long long sum = 0;
        long long mnsum = 0;
        for (int i : p) {
            sum += w[i];
            ans = max(ans, sum - mnsum);
            mnsum = min(mnsum, sum);
        }
    }

    cout << ans << '\n';

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 592 KB Output is correct
2 Correct 43 ms 592 KB Output is correct
3 Correct 44 ms 592 KB Output is correct
4 Correct 45 ms 592 KB Output is correct
5 Correct 46 ms 592 KB Output is correct
6 Correct 53 ms 592 KB Output is correct
7 Correct 41 ms 592 KB Output is correct
8 Correct 42 ms 760 KB Output is correct
9 Correct 42 ms 592 KB Output is correct
10 Correct 41 ms 592 KB Output is correct
11 Correct 1 ms 608 KB Output is correct
12 Incorrect 2 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 592 KB Output is correct
2 Correct 45 ms 592 KB Output is correct
3 Correct 41 ms 592 KB Output is correct
4 Correct 42 ms 764 KB Output is correct
5 Correct 41 ms 592 KB Output is correct
6 Correct 40 ms 760 KB Output is correct
7 Correct 45 ms 592 KB Output is correct
8 Correct 40 ms 592 KB Output is correct
9 Correct 41 ms 764 KB Output is correct
10 Correct 41 ms 592 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 592 KB Output is correct
2 Correct 45 ms 592 KB Output is correct
3 Correct 41 ms 592 KB Output is correct
4 Correct 42 ms 764 KB Output is correct
5 Correct 41 ms 592 KB Output is correct
6 Correct 40 ms 760 KB Output is correct
7 Correct 45 ms 592 KB Output is correct
8 Correct 40 ms 592 KB Output is correct
9 Correct 41 ms 764 KB Output is correct
10 Correct 41 ms 592 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 592 KB Output is correct
2 Correct 45 ms 592 KB Output is correct
3 Correct 41 ms 592 KB Output is correct
4 Correct 42 ms 764 KB Output is correct
5 Correct 41 ms 592 KB Output is correct
6 Correct 40 ms 760 KB Output is correct
7 Correct 45 ms 592 KB Output is correct
8 Correct 40 ms 592 KB Output is correct
9 Correct 41 ms 764 KB Output is correct
10 Correct 41 ms 592 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 592 KB Output is correct
2 Correct 43 ms 592 KB Output is correct
3 Correct 44 ms 592 KB Output is correct
4 Correct 45 ms 592 KB Output is correct
5 Correct 46 ms 592 KB Output is correct
6 Correct 53 ms 592 KB Output is correct
7 Correct 41 ms 592 KB Output is correct
8 Correct 42 ms 760 KB Output is correct
9 Correct 42 ms 592 KB Output is correct
10 Correct 41 ms 592 KB Output is correct
11 Correct 1 ms 608 KB Output is correct
12 Incorrect 2 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -