Submission #746276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
746276	2023-05-22T07:07:10 Z	nguyentunglam	Catfish Farm (IOI22_fish)	C++17	9 / 100	297 ms	46448 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);

    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) {
                int 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));
            }
        }
    }
//    cout << max(in[n - 1], de[n - 1]);

    return max(in[n - 1], de[n - 1]);
}

#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];

    long long ret = max_weights(n, m, x, y, w);
}
#endif // ngu

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	26944 KB	Output is correct
2	Correct	69 ms	30396 KB	Output is correct
3	Correct	30 ms	24496 KB	Output is correct
4	Correct	31 ms	24532 KB	Output is correct
5	Correct	260 ms	43380 KB	Output is correct
6	Correct	297 ms	46448 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	14420 KB	Output is correct
2	Correct	116 ms	33316 KB	Output is correct
3	Correct	134 ms	35884 KB	Output is correct
4	Correct	58 ms	28248 KB	Output is correct
5	Correct	70 ms	30388 KB	Output is correct
6	Correct	8 ms	14420 KB	Output is correct
7	Correct	8 ms	14404 KB	Output is correct
8	Correct	8 ms	14420 KB	Output is correct
9	Correct	8 ms	14436 KB	Output is correct
10	Correct	29 ms	24532 KB	Output is correct
11	Correct	32 ms	24572 KB	Output is correct
12	Correct	80 ms	28480 KB	Output is correct
13	Correct	91 ms	30456 KB	Output is correct
14	Correct	70 ms	28716 KB	Output is correct
15	Correct	81 ms	29992 KB	Output is correct
16	Correct	72 ms	28676 KB	Output is correct
17	Correct	82 ms	30276 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	24508 KB	Output is correct
2	Correct	29 ms	24600 KB	Output is correct
3	Incorrect	66 ms	25996 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '10556799894943'
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	24508 KB	Output is correct
2	Correct	29 ms	24600 KB	Output is correct
3	Incorrect	66 ms	25996 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '10556799894943'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	26944 KB	Output is correct
2	Correct	69 ms	30396 KB	Output is correct
3	Correct	30 ms	24496 KB	Output is correct
4	Correct	31 ms	24532 KB	Output is correct
5	Correct	260 ms	43380 KB	Output is correct
6	Correct	297 ms	46448 KB	Output is correct
7	Correct	8 ms	14420 KB	Output is correct
8	Correct	116 ms	33316 KB	Output is correct
9	Correct	134 ms	35884 KB	Output is correct
10	Correct	58 ms	28248 KB	Output is correct
11	Correct	70 ms	30388 KB	Output is correct
12	Correct	8 ms	14420 KB	Output is correct
13	Correct	8 ms	14404 KB	Output is correct
14	Correct	8 ms	14420 KB	Output is correct
15	Correct	8 ms	14436 KB	Output is correct
16	Correct	29 ms	24532 KB	Output is correct
17	Correct	32 ms	24572 KB	Output is correct
18	Correct	80 ms	28480 KB	Output is correct
19	Correct	91 ms	30456 KB	Output is correct
20	Correct	70 ms	28716 KB	Output is correct
21	Correct	81 ms	29992 KB	Output is correct
22	Correct	72 ms	28676 KB	Output is correct
23	Correct	82 ms	30276 KB	Output is correct
24	Correct	29 ms	24508 KB	Output is correct
25	Correct	29 ms	24600 KB	Output is correct
26	Incorrect	66 ms	25996 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '10556799894943'
27	Halted	0 ms	0 KB	-

Submission #746276

Compilation message