oj.uz

Submission #629236

# Submission time Handle Problem Language Result Execution time Memory
629236 2022-08-14T09:48:06 Z qwerasdfzxcl Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 38656 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], S[100100];
vector<ll> dp[2][100100];
int n, sz[100100];

ll cost(int i, int s, int e){
    if (s>e) 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] - (j1<0?0: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], -INF);
        dp[1][i].resize(sz[i], -INF);
    }

    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;

    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], dp[1][i-2][k] + cost(i-1, 0, 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 1093 ms 33212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12056 KB Output is correct
2 Execution timed out 1091 ms 38656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28008 KB Output is correct
2 Correct 50 ms 28084 KB Output is correct
3 Incorrect 98 ms 28796 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12000 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12020 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 12052 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Incorrect 7 ms 12124 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '173394817604'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12000 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12020 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 12052 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Incorrect 7 ms 12124 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '173394817604'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12000 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12020 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 12052 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Incorrect 7 ms 12124 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '173394817604'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28008 KB Output is correct
2 Correct 50 ms 28084 KB Output is correct
3 Incorrect 98 ms 28796 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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