oj.uz

Submission #1072436

# Submission time Handle Problem Language Result Execution time Memory
1072436 2024-08-23T19:03:40 Z vjudge1 Catfish Farm (IOI22_fish) C++17
6 / 100
 95 ms 21068 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
using vi = vector <int>;

// dp[i][j] = max grams caught if caught catfish until j from column i-1

// pier worth extending up to every catfish or until the end (O(n+m) optimal maximal piers)

const ll MAXN = 1E5+16, INF = ll(1E18)+16;
ll dp[MAXN];
vii ccs[MAXN];
ll max_weights (int n, int m, vi vx, vi vy, vi vw) {
    for (ll i = 0; i < m; i++)
        ccs[vx[i]].push_back({ vy[i]+1, vw[i] });
    for (ll x = 0; x < n; x++) {
        sort(ccs[x].begin(), ccs[x].end());
        ccs[x].insert(ccs[x].begin(), ii{ -1, 0 });
        // ps[x].push_back(0);
        ll acc = 0;
        for (auto &[y, w] : ccs[x]) {
            acc += w;
            w = acc;
        }
    }
    auto fget = [&](ll x, ll y) -> ll { // pier at column x up until y
        if (x < 0 || n <= x) return 0;
        return (upper_bound(ccs[x].begin(), ccs[x].end(), ii{ y, INF })-1)->second;
    };
    if (n == 2) return max(fget(0, 2), fget(1, 2));
    ll ans = fget(1, n); // all second column
    for (ll y = 0; y <= n; y++) {
        ans = max(ans, fget(0, y) + fget(1, n) - fget(1, y));
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9672 KB Output is correct
2 Correct 36 ms 10696 KB Output is correct
3 Correct 6 ms 5720 KB Output is correct
4 Correct 9 ms 5852 KB Output is correct
5 Incorrect 95 ms 21068 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '0'
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 58 ms 13380 KB Output is correct
3 Correct 69 ms 15676 KB Output is correct
4 Correct 30 ms 9664 KB Output is correct
5 Correct 47 ms 10680 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 2 ms 2648 KB Output is correct
10 Correct 6 ms 5724 KB Output is correct
11 Correct 6 ms 5804 KB Output is correct
12 Correct 30 ms 10180 KB Output is correct
13 Correct 38 ms 11488 KB Output is correct
14 Correct 32 ms 9956 KB Output is correct
15 Correct 34 ms 10948 KB Output is correct
16 Correct 32 ms 10184 KB Output is correct
17 Correct 35 ms 10940 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5720 KB Output is correct
2 Incorrect 6 ms 5720 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 Incorrect 2 ms 2788 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5720 KB Output is correct
2 Incorrect 6 ms 5720 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 Correct 31 ms 9672 KB Output is correct
2 Correct 36 ms 10696 KB Output is correct
3 Correct 6 ms 5720 KB Output is correct
4 Correct 9 ms 5852 KB Output is correct
5 Incorrect 95 ms 21068 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '0'
6 Halted 0 ms 0 KB -