Submission #1093461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1093461	2024-09-26T21:07:10 Z	selmahbn	Mobile (BOI12_mobile)	C++17	8 / 100	624 ms	40308 KB

mobile

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pdl pair<double, ll>

double sp(double x1, double y1, double x2, double y2) {
    double top = x2*x2 - x1*x1 + y2*y2 - y1*y1;
    double bottom = 2*x2 - 2*x1;
    return top/bottom;
}

int main()
{
    ll n; double l;
    cin >> n >> l;
    vector<pdl> p(n);
    ll li = -1;
    vector<double> x(n);
    vector<double> y(n);
    for (ll i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        double last;
        bool gleich = false;
        while (li >= 0) {
            double lsp, i2;
            tie(lsp, i2) = p[li];
            if (x[i] == x[i2]) {
                if (abs(y[i]) < abs(y[i2])) {
                    li--;
                    continue;
                } else {
                    gleich = true;
                    break;
                }
            }
            double csp = sp(x[i], y[i], x[i2], y[i2]);
            if (csp <= lsp) {
                li--;
            } else {
                last = csp;
                break;
            }
        }
        if (gleich) continue;
        if (li == -1) p[0] = make_pair(0, i);
        else p[li+1] = make_pair(last, i);
        li++;
    }
    double maxi = 0;
    ll last = p[0].second;
    for (ll i = 0; i <= li; i++) {
        double csp, ci;
        tie(csp, ci) = p[i];
        if (csp > l || i == li) {
            if (i == li && csp <= l) last = ci;
            double dist = sqrt((x[last]-l)*(x[last]-l)+y[last]*y[last]);
            maxi = max(maxi, dist);
            if (csp > l) break;
        }
        double dist = sqrt((x[ci]-csp)*(x[ci]-csp)+y[ci]*y[ci]);
        maxi = max(maxi, dist);
        last = ci;
    }
    cout << maxi;
    return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct

Subtask #3
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Incorrect	2 ms	348 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	604 KB	Output is correct
2	Incorrect	3 ms	604 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	600 KB	Output is correct
2	Incorrect	3 ms	600 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	604 KB	Output is correct
2	Incorrect	3 ms	604 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	3512 KB	Output is correct
2	Incorrect	50 ms	3408 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	3160 KB	Output is correct
2	Correct	36 ms	3268 KB	Output is correct
3	Incorrect	43 ms	3860 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	3672 KB	Output is correct
2	Incorrect	50 ms	3560 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	59 ms	4436 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	58 ms	4580 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	207 ms	18512 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	301 ms	20564 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	252 ms	22100 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	373 ms	24560 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	308 ms	25428 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	429 ms	28304 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	357 ms	29524 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	489 ms	32592 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	434 ms	36220 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	624 ms	40308 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Submission #1093461

Compilation message