oj.uz

Submission #741854

# Submission time Handle Problem Language Result Execution time Memory
741854 2023-05-15T02:13:31 Z fanwen Catfish Farm (IOI22_fish) C++17
0 / 100
 133 ms 29248 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()

#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

long long max_weights(int numCol, int numCatfish, vector <int> rows, vector <int> cols, vector <int> weights) {
    vector <vector <pair <int, long long>>> atCol(numCol);
    REP(i, numCatfish) {
        atCol[cols[i]].push_back(make_pair(rows[i], weights[i]));
    }
    REP(i, numCol) {

        sort(ALL(atCol[i]));
        atCol[i].emplace_back(numCol - 1, 0);
        long long pre = 0;
        for (auto &[_, x] : atCol[i]) {
            x += pre;
            pre = x;
        }
    }
    auto prefix_sum = [&] (int i, int cur) -> long long {
        auto it = lower_bound(ALL(atCol[i]), make_pair(cur, -1ll));
        if(it != atCol[i].begin()) return prev(it) -> second;
        return 0;
    };
    vector <vector <vector <long long>>> dp(numCol, vector <vector <long long>>(2));
    REP(i, numCol) {
        dp[i][0].resize((int) atCol[i].size(), 0);
        dp[i][1].resize((int) atCol[i].size(), 0);
        long long Max = 0;
        if(i == 0) continue;
        for (int cur = (int) atCol[i].size() - 1, pre = (int) atCol[i - 1].size(); cur >= 0; cur--) {
            while(pre > 0 && atCol[i - 1][pre - 1].first >= atCol[i][cur].first) {
                pre--;
                maximize(Max, dp[i - 1][0][pre] + prefix_sum(i, atCol[i - 1][pre].first));
            }
            maximize(dp[i][0][cur], Max - prefix_sum(i, atCol[i][cur].first));
        }
        Max = (i >= 2 ? max(*max_element(ALL(dp[i - 2][0])), *max_element(ALL(dp[i - 2][1]))) : 0);
        // if(i > 1) Max = max(*max_element(ALL(dp[i - 2][0])), *max_element(ALL(dp[i - 2][1])));
        // else Max = 0;
        Max = 0;
        for (int cur = 0, pre = -1; cur < (int) atCol[i].size(); ++cur) {
            while(pre + 1 < (int) atCol[i - 1].size() && atCol[i - 1][pre + 1].first <= atCol[i][cur].first) {
                pre++;
                maximize(Max, dp[i - 1][1][pre] - prefix_sum(i - 1, atCol[i - 1][pre].first));
            }
            // cout << cur << '\n';
            maximize(dp[i][1][cur], Max + prefix_sum(i - 1, atCol[i][cur].first));
        }
    }
    return max(*max_element(ALL(dp[numCol - 1][0])), *max_element(ALL(dp[numCol - 1][1])));
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 22096 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '999990243'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20576 KB Output is correct
2 Incorrect 33 ms 20520 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 220 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 300 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 220 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 300 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 220 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 300 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20576 KB Output is correct
2 Incorrect 33 ms 20520 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 22096 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '999990243'
2 Halted 0 ms 0 KB -