Submission #746285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
746285	2023-05-22T07:33:22 Z	nguyentunglam	Catfish Farm (IOI22_fish)	C++17	9 / 100	296 ms	39680 KB

fish

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 3e5 + 10;
int order[N];
vector<int> fish[N];
vector<long long> pref[N];
long long in[N], de[N], lastin[N], lastde[2][N];

long long calc(int h, int col) {
    if (h == -1 || col < 0 || fish[col].empty()) return 0;
    int idx = --upper_bound(fish[col].begin(), fish[col].end(), h) - fish[col].begin();
    return pref[col][idx];
}

long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {

    for(int i = 0; i < n; i++) fish[i].push_back(0), pref[i].push_back(0);

    for(int i = 0; i < m; i++) order[i] = i;
    sort(order, order + m, [&] (const int &A, const int &B) {
         return Y[A] < Y[B];
         });

    for(int cur = 0; cur < m; cur++) {
        int i = order[cur];
        fish[X[i]].push_back(Y[i]);
        pref[X[i]].push_back(pref[X[i]].back() + W[i]);
    }

    for(int i = 0; i < n; i++) fish[i].push_back(n + 1);

    de[0] = calc(n, 1);
    lastin[0] = calc(n, 0);
    lastde[1][0] = calc(n, 1);

    long long res = 0;

    for(int i = 1; i < n; i++) {
        for(int &preh : fish[i]) {
            int h = preh - 1;
            in[i] = max(in[i], in[i - 1] + calc(h, i - 1) - calc(h, i));
            de[i] = max(de[i], de[i - 1] - calc(h, i) + calc(h, i + 1));
            lastde[1][i] = max(lastde[1][i], de[i - 1] - calc(h, i) + calc(h, i + 1));
            lastde[0][i] = max(lastde[0][i], de[i - 1] - calc(h, i));
            lastin[i] = max(lastin[i], in[i] + calc(n, i) - calc(h, i));

            if (i >= 2) {
                long long tmp = max(lastde[1][i - 2], lastde[0][i - 2] + calc(h, i - 1));
                in[i] = max(in[i], tmp - calc(h, i));
                de[i] = max(de[i], lastin[i - 2] + calc(n, i) - calc(h, i) + calc(h, i + 1));
            }
            if (i == n - 1) {
                res = max({res, in[i - 1] + calc(h, i - 1), de[i - 1] - calc(h, i)});
                res = max(res, lastin[i - 2] + calc(n, i));
                res = max(res, lastde[0][i - 2] + calc(n, i - 1));
            }
        }
    }

    return res;
}

#ifdef ngu
int main() {

    freopen ("task.inp", "r", stdin);
    freopen ("task.out", "w", stdout);

    int n, m; cin >> n >> m;
    vector<int> x(m), y(m), w(m);
    for(int i = 0; i < m; i++) cin >> x[i] >> y[i] >> w[i];
    cout <<  max_weights(n, m, x, y, w);
}
#endif // ngu

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	26948 KB	Output is correct
2	Correct	70 ms	28652 KB	Output is correct
3	Correct	33 ms	24608 KB	Output is correct
4	Correct	39 ms	24580 KB	Output is correct
5	Correct	257 ms	37032 KB	Output is correct
6	Correct	296 ms	39680 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14420 KB	Output is correct
2	Correct	120 ms	30392 KB	Output is correct
3	Correct	138 ms	32472 KB	Output is correct
4	Correct	63 ms	26904 KB	Output is correct
5	Correct	73 ms	28624 KB	Output is correct
6	Correct	8 ms	14420 KB	Output is correct
7	Correct	8 ms	14440 KB	Output is correct
8	Correct	8 ms	14408 KB	Output is correct
9	Correct	8 ms	14420 KB	Output is correct
10	Correct	31 ms	24524 KB	Output is correct
11	Correct	31 ms	24516 KB	Output is correct
12	Correct	77 ms	26940 KB	Output is correct
13	Correct	102 ms	28740 KB	Output is correct
14	Correct	74 ms	27332 KB	Output is correct
15	Correct	80 ms	28384 KB	Output is correct
16	Correct	76 ms	27380 KB	Output is correct
17	Correct	85 ms	28700 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	24500 KB	Output is correct
2	Correct	30 ms	24532 KB	Output is correct
3	Incorrect	78 ms	24988 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '18225248275204'
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	24500 KB	Output is correct
2	Correct	30 ms	24532 KB	Output is correct
3	Incorrect	78 ms	24988 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '18225248275204'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	26948 KB	Output is correct
2	Correct	70 ms	28652 KB	Output is correct
3	Correct	33 ms	24608 KB	Output is correct
4	Correct	39 ms	24580 KB	Output is correct
5	Correct	257 ms	37032 KB	Output is correct
6	Correct	296 ms	39680 KB	Output is correct
7	Correct	9 ms	14420 KB	Output is correct
8	Correct	120 ms	30392 KB	Output is correct
9	Correct	138 ms	32472 KB	Output is correct
10	Correct	63 ms	26904 KB	Output is correct
11	Correct	73 ms	28624 KB	Output is correct
12	Correct	8 ms	14420 KB	Output is correct
13	Correct	8 ms	14440 KB	Output is correct
14	Correct	8 ms	14408 KB	Output is correct
15	Correct	8 ms	14420 KB	Output is correct
16	Correct	31 ms	24524 KB	Output is correct
17	Correct	31 ms	24516 KB	Output is correct
18	Correct	77 ms	26940 KB	Output is correct
19	Correct	102 ms	28740 KB	Output is correct
20	Correct	74 ms	27332 KB	Output is correct
21	Correct	80 ms	28384 KB	Output is correct
22	Correct	76 ms	27380 KB	Output is correct
23	Correct	85 ms	28700 KB	Output is correct
24	Correct	35 ms	24500 KB	Output is correct
25	Correct	30 ms	24532 KB	Output is correct
26	Incorrect	78 ms	24988 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '18225248275204'
27	Halted	0 ms	0 KB	-

Submission #746285

Compilation message