oj.uz

Submission #746355

# Submission time Handle Problem Language Result Execution time Memory
746355 2023-05-22T11:46:56 Z nguyentunglam Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 34788 KB 
#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 f[3][2][2][2];

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);

    bool pre = 0;
    memset(f, -61, sizeof(f));
    f[0][0][0][0] = 0;
    for(int i = 0; i < n; i++) {
        bool cur = pre ^ 1;
        for(int &preh : fish[i]) {
            int h = preh - 1;
            for(int x1 = 0; x1 < 3; x1++) for(int x2 = 0; x2 < 2; x2++) for(int x3 = 0; x3 < 2; x3++) {
                for(int y1 = 0; y1 < 3; y1++) for(int y2 = 0; y2 < 2; y2++) for(int y3 = 0; y3 < 2; y3++) {
                    bool ok = 1;
                    if (x2) ok &= y1 == 2;
                    if (y3) ok &= x1 == 1;

                    if (ok) {
                        f[x1][x2][x3][cur] = max(f[x1][x2][x3][cur], f[y1][y2][y3][pre] + x2 * calc(h, i - 1) + x3 * calc(h, i + 1) - (x1 > 0) * calc(h, i));
                    }
                }
            }
        }
        for(int x1 = 0; x1 < 3; x1++) for(int x2 = 0; x2 < 2; x2++) for(int x3 = 0; x3 < 2; x3++) f[x1][x2][x3][pre] = -1e18;
        pre = cur;
    }
    long long res = 0;
    for(int x1 = 0; x1 < 3; x1++) for(int x2 = 0; x2 < 2; x2++) for(int x3 = 0; x3 < 2; x3++) {
        res = max(res, f[x1][x2][x3][pre]);
    }
    return res;
}

#ifdef ngu
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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 23776 KB Output is correct
2 Correct 590 ms 24920 KB Output is correct
3 Correct 277 ms 20640 KB Output is correct
4 Correct 297 ms 20644 KB Output is correct
5 Execution timed out 1056 ms 33164 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 946 ms 27172 KB Output is correct
3 Execution timed out 1058 ms 28736 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 20648 KB Output is correct
2 Correct 304 ms 20644 KB Output is correct
3 Correct 305 ms 21632 KB Output is correct
4 Correct 331 ms 22292 KB Output is correct
5 Correct 453 ms 25024 KB Output is correct
6 Correct 420 ms 24364 KB Output is correct
7 Correct 423 ms 24948 KB Output is correct
8 Correct 434 ms 24972 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14400 KB Output is correct
2 Correct 8 ms 14280 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 10 ms 14356 KB Output is correct
6 Correct 11 ms 14312 KB Output is correct
7 Correct 8 ms 14292 KB Output is correct
8 Correct 9 ms 14292 KB Output is correct
9 Correct 12 ms 14408 KB Output is correct
10 Correct 16 ms 14540 KB Output is correct
11 Correct 13 ms 14456 KB Output is correct
12 Correct 12 ms 14456 KB Output is correct
13 Correct 9 ms 14292 KB Output is correct
14 Correct 14 ms 14464 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14400 KB Output is correct
2 Correct 8 ms 14280 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 10 ms 14356 KB Output is correct
6 Correct 11 ms 14312 KB Output is correct
7 Correct 8 ms 14292 KB Output is correct
8 Correct 9 ms 14292 KB Output is correct
9 Correct 12 ms 14408 KB Output is correct
10 Correct 16 ms 14540 KB Output is correct
11 Correct 13 ms 14456 KB Output is correct
12 Correct 12 ms 14456 KB Output is correct
13 Correct 9 ms 14292 KB Output is correct
14 Correct 14 ms 14464 KB Output is correct
15 Correct 10 ms 14400 KB Output is correct
16 Correct 16 ms 14536 KB Output is correct
17 Correct 215 ms 17052 KB Output is correct
18 Correct 179 ms 17512 KB Output is correct
19 Correct 172 ms 17356 KB Output is correct
20 Correct 156 ms 17332 KB Output is correct
21 Correct 161 ms 17364 KB Output is correct
22 Correct 337 ms 20340 KB Output is correct
23 Correct 36 ms 14932 KB Output is correct
24 Correct 124 ms 16216 KB Output is correct
25 Correct 13 ms 14408 KB Output is correct
26 Correct 43 ms 14852 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14400 KB Output is correct
2 Correct 8 ms 14280 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 10 ms 14356 KB Output is correct
6 Correct 11 ms 14312 KB Output is correct
7 Correct 8 ms 14292 KB Output is correct
8 Correct 9 ms 14292 KB Output is correct
9 Correct 12 ms 14408 KB Output is correct
10 Correct 16 ms 14540 KB Output is correct
11 Correct 13 ms 14456 KB Output is correct
12 Correct 12 ms 14456 KB Output is correct
13 Correct 9 ms 14292 KB Output is correct
14 Correct 14 ms 14464 KB Output is correct
15 Correct 10 ms 14400 KB Output is correct
16 Correct 16 ms 14536 KB Output is correct
17 Correct 215 ms 17052 KB Output is correct
18 Correct 179 ms 17512 KB Output is correct
19 Correct 172 ms 17356 KB Output is correct
20 Correct 156 ms 17332 KB Output is correct
21 Correct 161 ms 17364 KB Output is correct
22 Correct 337 ms 20340 KB Output is correct
23 Correct 36 ms 14932 KB Output is correct
24 Correct 124 ms 16216 KB Output is correct
25 Correct 13 ms 14408 KB Output is correct
26 Correct 43 ms 14852 KB Output is correct
27 Correct 29 ms 14596 KB Output is correct
28 Correct 917 ms 28716 KB Output is correct
29 Execution timed out 1070 ms 33620 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 20648 KB Output is correct
2 Correct 304 ms 20644 KB Output is correct
3 Correct 305 ms 21632 KB Output is correct
4 Correct 331 ms 22292 KB Output is correct
5 Correct 453 ms 25024 KB Output is correct
6 Correct 420 ms 24364 KB Output is correct
7 Correct 423 ms 24948 KB Output is correct
8 Correct 434 ms 24972 KB Output is correct
9 Correct 455 ms 24744 KB Output is correct
10 Correct 338 ms 24344 KB Output is correct
11 Correct 653 ms 34316 KB Output is correct
12 Correct 8 ms 14292 KB Output is correct
13 Correct 8 ms 14384 KB Output is correct
14 Correct 7 ms 14292 KB Output is correct
15 Correct 7 ms 14404 KB Output is correct
16 Correct 9 ms 14404 KB Output is correct
17 Correct 9 ms 14292 KB Output is correct
18 Correct 344 ms 20640 KB Output is correct
19 Correct 392 ms 20648 KB Output is correct
20 Correct 318 ms 20640 KB Output is correct
21 Correct 417 ms 20644 KB Output is correct
22 Correct 863 ms 27056 KB Output is correct
23 Correct 866 ms 34188 KB Output is correct
24 Correct 922 ms 34788 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 23776 KB Output is correct
2 Correct 590 ms 24920 KB Output is correct
3 Correct 277 ms 20640 KB Output is correct
4 Correct 297 ms 20644 KB Output is correct
5 Execution timed out 1056 ms 33164 KB Time limit exceeded
6 Halted 0 ms 0 KB -