oj.uz

답안 #741859

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
741859 2023-05-15T02:16:02 Z fanwen 메기 농장 (IOI22_fish) C++17
0 / 100
 107 ms 26444 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, 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 > 1 ? max(*max_element(ALL(dp[i - 2][0])), *max_element(ALL(dp[i - 2][1]))) : 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 22092 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '24806557567238'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 107 ms 26444 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '46804015619258'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 20564 KB Output is correct
2 Correct 31 ms 20660 KB Output is correct
3 Incorrect 50 ms 22484 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 20564 KB Output is correct
2 Correct 31 ms 20660 KB Output is correct
3 Incorrect 50 ms 22484 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 22092 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '24806557567238'
2 Halted 0 ms 0 KB -