oj.uz

Submission #746284

# Submission time Handle Problem Language Result Execution time Memory
746284 2023-05-22T07:18:32 Z nguyentunglam Catfish Farm (IOI22_fish) C++17
3 / 100
 282 ms 39800 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 in[N], de[N], lastin[N], lastde[2][N];

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

    de[0] = calc(n, 1);

    for(int i = 1; i <= n; i++) {
        for(int &preh : fish[i]) {
            int h = preh - 1;
            in[i] = max(in[i], in[i - 1] + calc(h, i - 1) - calc(h, i));
            de[i] = max(de[i], de[i - 1] - calc(h, i) + calc(h, i + 1));
            lastde[1][i] = max(lastde[1][i], de[i - 1] - calc(h, i) + calc(h, i + 1));
            lastde[0][i] = max(lastde[0][i], de[i - 1] - calc(h, i));
            lastin[i] = max(lastin[i], in[i] + calc(n, i) - calc(h, i));

            if (i > 2) {
                long long tmp = max(lastde[1][i - 2], lastde[0][i - 2] + calc(h, i - 1));
                in[i] = max(in[i], tmp - calc(h, i));
                de[i] = max(de[i], lastin[i - 2] + calc(n, i) - calc(h, i) + calc(h, i + 1));
            }
        }
    }
//    cout << max(in[n - 1], de[n - 1]);

    return max(in[n], de[n]);
}

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

# Verdict Execution time Memory Grader output
1 Correct 59 ms 26908 KB Output is correct
2 Correct 68 ms 28636 KB Output is correct
3 Correct 31 ms 24508 KB Output is correct
4 Correct 30 ms 24580 KB Output is correct
5 Correct 251 ms 36980 KB Output is correct
6 Correct 282 ms 39800 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 116 ms 30388 KB Output is correct
3 Correct 138 ms 32456 KB Output is correct
4 Correct 59 ms 26844 KB Output is correct
5 Correct 68 ms 28608 KB Output is correct
6 Incorrect 10 ms 14420 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24524 KB Output is correct
2 Correct 31 ms 24544 KB Output is correct
3 Incorrect 60 ms 25052 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '18225035644282'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14392 KB Output is correct
2 Correct 9 ms 14440 KB Output is correct
3 Incorrect 7 ms 14420 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14392 KB Output is correct
2 Correct 9 ms 14440 KB Output is correct
3 Incorrect 7 ms 14420 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14392 KB Output is correct
2 Correct 9 ms 14440 KB Output is correct
3 Incorrect 7 ms 14420 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24524 KB Output is correct
2 Correct 31 ms 24544 KB Output is correct
3 Incorrect 60 ms 25052 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '18225035644282'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 26908 KB Output is correct
2 Correct 68 ms 28636 KB Output is correct
3 Correct 31 ms 24508 KB Output is correct
4 Correct 30 ms 24580 KB Output is correct
5 Correct 251 ms 36980 KB Output is correct
6 Correct 282 ms 39800 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 116 ms 30388 KB Output is correct
9 Correct 138 ms 32456 KB Output is correct
10 Correct 59 ms 26844 KB Output is correct
11 Correct 68 ms 28608 KB Output is correct
12 Incorrect 10 ms 14420 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
13 Halted 0 ms 0 KB -