oj.uz

Submission #629261

# Submission time Handle Problem Language Result Execution time Memory
629261 2022-08-14T10:12:42 Z qwerasdfzxcl Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 47620 KB 
#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF = 4e18;
vector<int> H[100100], A[100100];
vector<ll> dp[2][100100], S[100100];
int n, sz[100100];

ll cost(int i, int s, int e){
    if (s>e || i==0) return 0;
    int j1 = upper_bound(H[i].begin(), H[i].end(), s-1) - H[i].begin() - 1;
    int j2 = upper_bound(H[i].begin(), H[i].end(), e) - H[i].begin() - 1;
    return S[i][j2] - S[i][j1];
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    n = N;
    for (int i=0;i<=N;i++) {H[i].push_back(0); H[i].push_back(N);}
    for (int i=0;i<M;i++){
        ++X[i], ++Y[i];
        H[X[i]].push_back(Y[i]);
        H[X[i]].push_back(Y[i]-1);
        if (X[i]>1) H[X[i]-1].push_back(Y[i]);
        if (X[i]<N) H[X[i]+1].push_back(Y[i]);
    }


    for (int i=0;i<=N;i++){
        sort(H[i].begin(), H[i].end());
        H[i].erase(unique(H[i].begin(), H[i].end()), H[i].end());
        sz[i] = H[i].size();

        A[i].resize(sz[i], 0);
        S[i].resize(sz[i], 0);
        dp[0][i].resize(sz[i], 0);
        dp[1][i].resize(sz[i], 0);
    }

    for (int i=0;i<M;i++){
        int idx = lower_bound(H[X[i]].begin(), H[X[i]].end(), Y[i]) - H[X[i]].begin();
        assert(idx < sz[X[i]]);
        A[X[i]][idx] = W[i];
    }


    for (int i=1;i<=n;i++){
        for (int j=1;j<sz[i];j++) S[i][j] = S[i][j-1] + A[i][j];
    }


    dp[0][0][0] = 0;
    dp[1][0][0] = 0;
    assert(sz[0]==2);
    dp[0][0][1] = -INF;
    dp[1][0][1] = -INF;

    for (int i=1;i<=n;i++){
        for (int j=0;j<sz[i];j++){
            ///0 -> 0
            for (int k=0;k<sz[i-1] && H[i-1][k]<=H[i][j];k++){
                dp[0][i][j] = max(dp[0][i][j], dp[0][i-1][k] + cost(i-1, H[i-1][k]+1, H[i][j]));
            }

            ///1 -> 0
            if (i>=2){
                for (int k=0;k<sz[i-2];k++){
                    dp[0][i][j] = max(dp[0][i][j], max(dp[0][i-2][k], dp[1][i-2][k]) + cost(i-1, 1, max(H[i-2][k], H[i][j])));
                }
            }

            ///0 -> 1
            dp[1][i][j] = max(dp[1][i][j], dp[0][i-1][sz[i-1]-1] + cost(i, H[i][j]+1, n));

            ///1 -> 1
            for (int k=0;k<sz[i-1];k++) if (H[i-1][k] >= H[i][j]) dp[1][i][j] = max(dp[1][i][j], dp[1][i-1][k] + cost(i, H[i][j]+1, H[i-1][k]));
        }
    }

    //printf(" %lld %lld %lld\n", H[1][0], H[1][1], H[1][2]);
    //printf(" %lld -> %lld(%d)\n", cost(1, 1, 1), dp[0][2][1], H[2][1]);

    return max(*max_element(dp[0][n].begin(), dp[0][n].end()), *max_element(dp[1][n].begin(), dp[1][n].end()));
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11988 KB Output is correct
2 Execution timed out 1093 ms 39668 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 28076 KB Output is correct
2 Correct 52 ms 28084 KB Output is correct
3 Correct 102 ms 29328 KB Output is correct
4 Correct 87 ms 29764 KB Output is correct
5 Correct 148 ms 32588 KB Output is correct
6 Correct 165 ms 32932 KB Output is correct
7 Correct 140 ms 32908 KB Output is correct
8 Correct 151 ms 32960 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12060 KB Output is correct
2 Correct 7 ms 11992 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 9 ms 12196 KB Output is correct
13 Correct 7 ms 12052 KB Output is correct
14 Correct 8 ms 12076 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12060 KB Output is correct
2 Correct 7 ms 11992 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 9 ms 12196 KB Output is correct
13 Correct 7 ms 12052 KB Output is correct
14 Correct 8 ms 12076 KB Output is correct
15 Correct 7 ms 12116 KB Output is correct
16 Correct 22 ms 12244 KB Output is correct
17 Execution timed out 1070 ms 15872 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12060 KB Output is correct
2 Correct 7 ms 11992 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 9 ms 12196 KB Output is correct
13 Correct 7 ms 12052 KB Output is correct
14 Correct 8 ms 12076 KB Output is correct
15 Correct 7 ms 12116 KB Output is correct
16 Correct 22 ms 12244 KB Output is correct
17 Execution timed out 1070 ms 15872 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 28076 KB Output is correct
2 Correct 52 ms 28084 KB Output is correct
3 Correct 102 ms 29328 KB Output is correct
4 Correct 87 ms 29764 KB Output is correct
5 Correct 148 ms 32588 KB Output is correct
6 Correct 165 ms 32932 KB Output is correct
7 Correct 140 ms 32908 KB Output is correct
8 Correct 151 ms 32960 KB Output is correct
9 Correct 235 ms 37740 KB Output is correct
10 Correct 141 ms 27832 KB Output is correct
11 Correct 284 ms 43096 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 7 ms 11988 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 7 ms 11988 KB Output is correct
17 Correct 6 ms 11988 KB Output is correct
18 Correct 49 ms 28056 KB Output is correct
19 Correct 52 ms 28088 KB Output is correct
20 Correct 51 ms 27980 KB Output is correct
21 Correct 59 ms 28080 KB Output is correct
22 Correct 361 ms 41520 KB Output is correct
23 Correct 405 ms 46992 KB Output is correct
24 Correct 415 ms 47620 KB Output is correct

Subtask #8
0 / 16.0

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