oj.uz

Submission #1002633

# Submission time Handle Problem Language Result Execution time Memory
1002633 2024-06-19T17:14:59 Z overwatch9 Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 228944 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector <vector <pair <int, ll>>> fish;
vector <vector <ll>> pfx;
int n, m;
const int maxn = 300 + 5;
ll dp[maxn][maxn][maxn];
bool ready[maxn][maxn][maxn];
ll found[maxn][maxn][maxn];
ll cost(int i, int h1, int h2, int h3) {
    if (i-1 <= 0 || max(h1, h3) <= h2 || (int)fish[i-1].size() == 1)
        return 0;
    int mx = max(h1, h3);
    if (found[i][h2][mx] != -1)
        return found[i][h2][mx];
    pair <int, ll> tp = {h2+1, 0};
    int it = lower_bound(fish[i-1].begin(), fish[i-1].end(), tp) - fish[i-1].begin();
    tp.first = mx;
    tp.second = 1e18;
    int it2 = upper_bound(fish[i-1].begin(), fish[i-1].end(), tp) - fish[i-1].begin();
    it2--;
    ll ans = 0;
    if (it == 0)
        ans = pfx[i-1][it2];
    ans = pfx[i-1][it2] - pfx[i-1][it-1];
    found[i][h2][mx] = ans;
    return ans;
}
ll solve(int i, int h1, int h2) {
    if (min(h1, h2) < 0 || max(h1, h2) > n)
        return 0;
    if (i == n+1) {
        return cost(i, h1, h2, 0);
        // return 0;
    }
    if (ready[i][h1][h2])
        return dp[i][h1][h2];
    ll ans = solve(i+1, h2, 0) + cost(i, h1, h2, 0);
    if (i-1 >= 1) {
        for (auto j : fish[i-1]) {
            if (h2 < h1 && h2 > 0 && j.first > h2)
                break;
            ans = max(ans, solve(i+1, h2, j.first) + cost(i, h1, h2, j.first));
            // ans = max(ans, solve(i+1, h2, j.first-1) + cost(i, h1, h2, j.first-1));
            // ans = max(ans, solve(i+1, h2, j.first+1) + cost(i, h1, h2, j.first+1));
        }
    }
    for (auto j : fish[i]) {
        if (h2 < h1 && h2 > 0 && j.first > h2)
            break;
        ans = max(ans, solve(i+1, h2, j.first) + cost(i, h1, h2, j.first));
        // ans = max(ans, solve(i+1, h2, j.first-1) + cost(i, h1, h2, j.first-1));
        // ans = max(ans, solve(i+1, h2, j.first+1) + cost(i, h1, h2, j.first+1));
    }
    if (i+1 <= n) {
        for (auto j : fish[i+1]) {
            if (h2 < h1 && h2 > 0 && j.first > h2)
                break;
            ans = max(ans, solve(i+1, h2, j.first) + cost(i, h1, h2, j.first));
            // ans = max(ans, solve(i+1, h2, j.first-1) + cost(i, h1, h2, j.first-1));
            // ans = max(ans, solve(i+1, h2, j.first+1) + cost(i, h1, h2, j.first+1));
        }
    }
    ready[i][h1][h2] = true;
    dp[i][h1][h2] = ans;
    return ans;
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n = N;
    m = M;
    fish.resize(N+1);
    pfx.resize(N+1);
    for (int i = 0; i < M; i++) {
        fish[X[i] + 1].push_back({Y[i] + 1, W[i]});
    }
    for (int i = 0; i <= N+1; i++) {
        for (int j = 0; j <= N+1; j++) {
            for (int k = 0; k <= N+1; k++)
                found[i][j][k] = -1;
        }
    }
    // dp = vector <vector <ll>> (N+1, vector <ll> (N+1, -1));
    for (int i = 1; i <= N; i++) {
        fish[i].push_back({0, 0});
        sort(fish[i].begin(), fish[i].end());
        pfx[i].resize((int)fish[i].size() + 5, 1e18);
        pfx[i][0] = 0;
        for (int j = 1; j < (int)fish[i].size(); j++)
            pfx[i][j] = pfx[i][j-1] + fish[i][j].second;
    }
    return solve(1, 0, 0);
}
// int main() {
//     freopen("in.txt", "r", stdin);
//     int nn, mm;
//     cin >> nn >> mm;
//     vector <int> x(mm), y(mm), w(mm);
//     for (int i = 0; i < mm; i++)
//         cin >> x[i] >> y[i] >> w[i];
//     cout << max_weights(nn, mm, x, y, w) << '\n';
// }

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 189124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1094 ms 197104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 169808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 432 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 19 ms 59256 KB Output is correct
10 Correct 81 ms 228944 KB Output is correct
11 Correct 19 ms 60764 KB Output is correct
12 Correct 73 ms 228356 KB Output is correct
13 Correct 6 ms 16216 KB Output is correct
14 Correct 70 ms 225876 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 432 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 19 ms 59256 KB Output is correct
10 Correct 81 ms 228944 KB Output is correct
11 Correct 19 ms 60764 KB Output is correct
12 Correct 73 ms 228356 KB Output is correct
13 Correct 6 ms 16216 KB Output is correct
14 Correct 70 ms 225876 KB Output is correct
15 Correct 72 ms 226900 KB Output is correct
16 Correct 155 ms 23376 KB Output is correct
17 Execution timed out 1062 ms 225600 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 432 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 19 ms 59256 KB Output is correct
10 Correct 81 ms 228944 KB Output is correct
11 Correct 19 ms 60764 KB Output is correct
12 Correct 73 ms 228356 KB Output is correct
13 Correct 6 ms 16216 KB Output is correct
14 Correct 70 ms 225876 KB Output is correct
15 Correct 72 ms 226900 KB Output is correct
16 Correct 155 ms 23376 KB Output is correct
17 Execution timed out 1062 ms 225600 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 169808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 189124 KB Time limit exceeded
2 Halted 0 ms 0 KB -