oj.uz

Submission #746275

# Submission time Handle Problem Language Result Execution time Memory
746275 2023-05-22T07:06:28 Z nguyentunglam Catfish Farm (IOI22_fish) C++17
0 / 100
 59 ms 27984 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], 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) {
                int 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 - 1], de[n - 1]);
}

#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];

    long long ret = max_weights(n, m, x, y, w);
}
#endif // ngu

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 27984 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14420 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 24524 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14320 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14320 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14320 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 24524 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 27984 KB Possible tampering with the output
2 Halted 0 ms 0 KB -