oj.uz

Submission #1076207

# Submission time Handle Problem Language Result Execution time Memory
1076207 2024-08-26T11:46:45 Z vjudge1 Catfish Farm (IOI22_fish) C++17
0 / 100
 102 ms 22708 KB 
#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using vll = vector<ll>;

struct AIB {
    int n;
    bool rev;
    vll V;

    AIB(int N, bool RV) : n(N + 1), rev(RV), V(N + 1, 0) {}

    void update(int p, ll v) {
        if(rev) p = n - p - 1;
        ++p;
        while(p < n) {
            V[p] = max(V[p], v);
            p += p & -p;
        }
    }

    ll query(int p) {
        if(rev) p = n - p - 1;
        ++p;
        ll re = 0;
        while(p) {
            re = max(re, V[p]);
            p -= p & -p;
        }
        return re;
    }
};

ll max_weights(int n, int m, vi X, vi Y, vi W) {
    vector<vector<ii> > A(n);
    for(int i = 0; i < m; ++i) 
        A[X[i]].push_back({Y[i], W[i]});
    for(int i = 0; i < n; ++i) {
        sort(A[i].begin(), A[i].end());
    }

    vll DP_tot(n, 0), DP0(n, 0), DP1(n, 0);

    AIB MaPre(n, 0), MaSuf(n, 1);

    ll re = 0;
    for(int i = 0; i < n; ++i) {
        ll rez_min = 0;
        if(i > 1) rez_min = DP_tot[i - 2];

        reverse(A[i].begin(), A[i].end());
        if(i) {
            for(auto [y, w] : A[i]) {
                ll re1 = rez_min;
                if(MaSuf.query(y + 1) > re1) re1 = MaSuf.query(y + 1);

                re1 += w;

                MaSuf.update(y, re1);
                MaPre.update(y, re1);
                DP1[i] = max(DP1[i], re1);
            }
        }

        reverse(A[i].begin(), A[i].end());
        if(i + 1 < n) {
            for(auto [y, w] : A[i]) { /// urcam, facem 0
                ll re0 = rez_min;
                if(MaPre.query(y - 1) > re0) re0 = MaPre.query(y - 1);

                re0 += w;

                MaPre.update(y, re0);
                DP0[i] = max(DP0[i], re0);
            }
        }


        DP_tot[i] = max(DP0[i], DP1[i]);
        if(i) DP_tot[i] = max(DP_tot[i], DP_tot[i - 1]);
        re = max(re, DP_tot[i]);
    }
    return re;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9924 KB Output is correct
2 Correct 40 ms 11564 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Incorrect 102 ms 22708 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '299626719225511'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 54 ms 13908 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80957761098360'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 4 ms 6488 KB Output is correct
3 Incorrect 23 ms 9964 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 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 348 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '285336762627'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 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 348 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '285336762627'
10 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 348 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 348 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '285336762627'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 4 ms 6488 KB Output is correct
3 Incorrect 23 ms 9964 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9924 KB Output is correct
2 Correct 40 ms 11564 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Incorrect 102 ms 22708 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '299626719225511'
6 Halted 0 ms 0 KB -