oj.uz

Submission #699064

# Submission time Handle Problem Language Result Execution time Memory
699064 2023-02-15T13:47:59 Z dxz05 Catfish Farm (IOI22_fish) C++17
9 / 100
 754 ms 77540 KB 
// #pragma GCC optimize("Ofast,O2,O3")
// #pragma GCC target("avx,avx2")

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define MP make_pair

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector<vector<pair<int, int>>> fish(N);
    vector<vector<ll>> sum(N);

    int MaxL = 10;

    vector<vector<ll>> pref(N, vector<ll>(MaxL + 1, 0));

    for (int i = 0; i < M; i++){
        ++Y[i];
        fish[X[i]].emplace_back(Y[i], W[i]);
        pref[X[i]][Y[i]] += W[i];
    }

    for (int i = 0; i < N; i++){
        for (int j = 1; j <= MaxL; j++) pref[i][j] += pref[i][j - 1];

        sort(fish[i].begin(), fish[i].end());
        int k = (int)fish[i].size();
        sum[i].resize(k);
        for (int j = 0; j < k; j++){
            sum[i][j] = fish[i][j].second;
            if (j > 0) sum[i][j] += sum[i][j - 1];
        }
    }

    function<ll(int, int, int)> get_sum = [&](int i, int l, int r){ // sum of fish with X = i, l <= Y <= r
        if (l > r) return 0ll;
        r = min(r, MaxL);
        l = max(l, 0);
        return pref[i][r] - (l == 0 ? 0ll : pref[i][l - 1]);

        int pl = lower_bound(fish[i].begin(), fish[i].end(), MP(l, 0)) - fish[i].begin();
        int pr = lower_bound(fish[i].begin(), fish[i].end(), MP(r + 1, 0)) - fish[i].begin() - 1;
        if (pl > pr) return 0ll;
        return sum[i][pr] - (pl > 0 ? sum[i][pl - 1] : 0ll);
    };

    vector<vector<ll>> dpl(N, vector<ll>(MaxL + 1, 0));
    for (int i = 1; i < N; i++){
        for (int l = 0; l <= MaxL; l++){
            for (int j = 0; j <= MaxL; j++){
                dpl[i][l] = max(dpl[i][l], dpl[i - 1][j] + get_sum(i - 1, j + 1, l));
            }
            for (int j = 0; j <= MaxL; j++){
                if (i >= 2) dpl[i][l] = max(dpl[i][l], dpl[i - 2][j] + get_sum(i - 1, 1, max(l, j)));
            }
        }
    }

    vector<vector<ll>> dpr(N, vector<ll>(MaxL + 1, 0));
    for (int i = N - 2; i >= 0; i--){
        for (int l = 0; l <= MaxL; l++){
            for (int j = 0; j <= MaxL; j++){
                dpr[i][l] = max(dpr[i][l], dpr[i + 1][j] + get_sum(i + 1, j + 1, l));
            }
            for (int j = 0; j <= MaxL; j++){
                if (i + 2 < N) dpr[i][l] = max(dpr[i][l], dpr[i + 2][j] + get_sum(i + 1, 1, max(l, j)));
            }
        }
    }

    ll res = 0;
    for (int i = 0; i < N; i++){
        for (int l = 0; l <= MaxL; l++){
            res = max(res, dpl[i][l] + dpr[i][l]);
        }
    }

    for (int i = 0; i + 1 < N; i++){
        for (int l1 = 0; l1 <= MaxL; l1++){
            for (int l2 = 0; l2 <= MaxL; l2++){
                ll cur = dpl[i][l1] + dpr[i + 1][l2];

                cur += get_sum(i, l1 + 1, l2);
                cur += get_sum(i + 1, l2 + 1, l1);

                res = max(res, cur);
            }
        }
    }

    for (int i = 1; i + 1 < N; i++){
        for (int l1 = 0; l1 <= MaxL; l1++){
            for (int l2 = 0; l2 <= MaxL; l2++){
                ll cur = dpl[i - 1][l1] + dpr[i + 1][l2];

                cur += get_sum(i, 1, max(l1, l2));

                res = max(res, cur);
            }
        }
    }

    for (int i = 1; i + 2 < N; i++){
        for (int l1 = 0; l1 <= MaxL; l1++){
            for (int l2 = 0; l2 <= MaxL; l2++){
                ll cur = dpl[i - 1][l1] + dpr[i + 2][l2];

                cur += get_sum(i, 1, l1);
                cur += get_sum(i + 1, 1, l2);

                res = max(res, cur);
            }
        }
    }

    return res;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 660 ms 71132 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 707 ms 77540 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 40212 KB Output is correct
2 Correct 698 ms 40216 KB Output is correct
3 Correct 655 ms 41804 KB Output is correct
4 Correct 696 ms 43952 KB Output is correct
5 Correct 738 ms 50360 KB Output is correct
6 Correct 735 ms 49892 KB Output is correct
7 Correct 749 ms 50396 KB Output is correct
8 Correct 754 ms 50408 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Incorrect 2 ms 340 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278323186206'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Incorrect 2 ms 340 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278323186206'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Incorrect 2 ms 340 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278323186206'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 40212 KB Output is correct
2 Correct 698 ms 40216 KB Output is correct
3 Correct 655 ms 41804 KB Output is correct
4 Correct 696 ms 43952 KB Output is correct
5 Correct 738 ms 50360 KB Output is correct
6 Correct 735 ms 49892 KB Output is correct
7 Correct 749 ms 50396 KB Output is correct
8 Correct 754 ms 50408 KB Output is correct
9 Runtime error 48 ms 39800 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 660 ms 71132 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -