Submission #627431

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
627431	2022-08-12T14:59:36 Z	imeimi2000	Catfish Farm (IOI22_fish)	C++17	9 / 100	298 ms	18168 KB

fish

#include "fish.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n;
vector<pii> P[100005];

struct segtree {
    ll seg[1 << 18];
    void init() {
        memset(seg, 0xcf, sizeof(seg));
    }
    void update(int i, int s, int e, int x, int y, ll v) {
        if (e < x || y < s) return;
        if (x <= s && e <= y) {
            seg[i] = max(seg[i], v);
            return;
        }
        int m = (s + e) / 2;
        update(i + i, s, m, x, y, v);
        update(i + i + 1, m + 1, e, x, y, v);
    }
    ll query(int i, int s, int e, int x) {
        if (s == e) return seg[i];
        int m = (s + e) / 2;
        if (x <= m) return max(seg[i], query(i + i, s, m, x));
        return max(seg[i], query(i + i + 1, m + 1, e, x));
    }
} up, dn;

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N;
    for (int i = 0; i < M; ++i) {
        P[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
    }
    ll p = 0;
    dn.init();
    for (int i = 1; i <= n; ++i) {
        sort(P[i].begin(), P[i].end());
        for (auto [j, v] : P[i]) {
            up.update(1, 0, n + 1, j + 1, n + 1, up.query(1, 0, n + 1, j) + v);
        }
        reverse(P[i].begin(), P[i].end());
        for (auto [j, v] : P[i]) {
            dn.update(1, 0, n + 1, 0, j - 1, dn.query(1, 0, n + 1, j) + v);
        }
        ll nxt = up.query(1, 0, n + 1, n + 1);
        up.update(1, 0, n + 1, 0, n + 1, dn.query(1, 0, n + 1, 0));
        dn.update(1, 0, n + 1, 0, n + 1, p);
        p = nxt;
    }
    return dn.query(1, 0, n + 1, 0);
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	9408 KB	Output is correct
2	Correct	72 ms	9888 KB	Output is correct
3	Correct	11 ms	4692 KB	Output is correct
4	Correct	10 ms	4712 KB	Output is correct
5	Correct	203 ms	16384 KB	Output is correct
6	Correct	298 ms	18168 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4692 KB	Output is correct
2	Correct	117 ms	12000 KB	Output is correct
3	Correct	141 ms	14148 KB	Output is correct
4	Correct	64 ms	10184 KB	Output is correct
5	Correct	95 ms	10912 KB	Output is correct
6	Correct	3 ms	4692 KB	Output is correct
7	Correct	2 ms	4692 KB	Output is correct
8	Correct	2 ms	4692 KB	Output is correct
9	Correct	2 ms	4692 KB	Output is correct
10	Correct	10 ms	4692 KB	Output is correct
11	Correct	10 ms	4716 KB	Output is correct
12	Correct	64 ms	10292 KB	Output is correct
13	Correct	83 ms	10916 KB	Output is correct
14	Correct	71 ms	10296 KB	Output is correct
15	Correct	72 ms	9664 KB	Output is correct
16	Correct	64 ms	10400 KB	Output is correct
17	Correct	74 ms	10600 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	4692 KB	Output is correct
2	Correct	13 ms	4640 KB	Output is correct
3	Incorrect	46 ms	7636 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4692 KB	Output is correct
2	Correct	3 ms	4692 KB	Output is correct
3	Correct	3 ms	4692 KB	Output is correct
4	Correct	3 ms	4692 KB	Output is correct
5	Correct	4 ms	4692 KB	Output is correct
6	Correct	3 ms	4692 KB	Output is correct
7	Correct	4 ms	4692 KB	Output is correct
8	Correct	3 ms	4692 KB	Output is correct
9	Incorrect	3 ms	4692 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4692 KB	Output is correct
2	Correct	3 ms	4692 KB	Output is correct
3	Correct	3 ms	4692 KB	Output is correct
4	Correct	3 ms	4692 KB	Output is correct
5	Correct	4 ms	4692 KB	Output is correct
6	Correct	3 ms	4692 KB	Output is correct
7	Correct	4 ms	4692 KB	Output is correct
8	Correct	3 ms	4692 KB	Output is correct
9	Incorrect	3 ms	4692 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4692 KB	Output is correct
2	Correct	3 ms	4692 KB	Output is correct
3	Correct	3 ms	4692 KB	Output is correct
4	Correct	3 ms	4692 KB	Output is correct
5	Correct	4 ms	4692 KB	Output is correct
6	Correct	3 ms	4692 KB	Output is correct
7	Correct	4 ms	4692 KB	Output is correct
8	Correct	3 ms	4692 KB	Output is correct
9	Incorrect	3 ms	4692 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	4692 KB	Output is correct
2	Correct	13 ms	4640 KB	Output is correct
3	Incorrect	46 ms	7636 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	9408 KB	Output is correct
2	Correct	72 ms	9888 KB	Output is correct
3	Correct	11 ms	4692 KB	Output is correct
4	Correct	10 ms	4712 KB	Output is correct
5	Correct	203 ms	16384 KB	Output is correct
6	Correct	298 ms	18168 KB	Output is correct
7	Correct	2 ms	4692 KB	Output is correct
8	Correct	117 ms	12000 KB	Output is correct
9	Correct	141 ms	14148 KB	Output is correct
10	Correct	64 ms	10184 KB	Output is correct
11	Correct	95 ms	10912 KB	Output is correct
12	Correct	3 ms	4692 KB	Output is correct
13	Correct	2 ms	4692 KB	Output is correct
14	Correct	2 ms	4692 KB	Output is correct
15	Correct	2 ms	4692 KB	Output is correct
16	Correct	10 ms	4692 KB	Output is correct
17	Correct	10 ms	4716 KB	Output is correct
18	Correct	64 ms	10292 KB	Output is correct
19	Correct	83 ms	10916 KB	Output is correct
20	Correct	71 ms	10296 KB	Output is correct
21	Correct	72 ms	9664 KB	Output is correct
22	Correct	64 ms	10400 KB	Output is correct
23	Correct	74 ms	10600 KB	Output is correct
24	Correct	10 ms	4692 KB	Output is correct
25	Correct	13 ms	4640 KB	Output is correct
26	Incorrect	46 ms	7636 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
27	Halted	0 ms	0 KB	-

Submission #627431

Compilation message