oj.uz

Submission #1002370

# Submission time Handle Problem Language Result Execution time Memory
1002370 2024-06-19T13:43:46 Z overwatch9 Catfish Farm (IOI22_fish) C++17
6 / 100
 94 ms 34984 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector <vector <pair <int, ll>>> fish;
vector <vector <ll>> pfx;
int n, m;
ll get_sum(int l, int r, int col) {
    pair <int, ll> tp = {l, 0};
    // for (auto j : fish[col])
    //     cout << j.first << '\n';
    int it = upper_bound(fish[col].begin(), fish[col].end(), tp) - fish[col].begin();
    it--;
    // cout << "IT1: " << it << '\n';
    tp.first = r+1;
    int it2 = upper_bound(fish[col].begin(), fish[col].end(), tp) - fish[col].begin();
    it2--;
    // cout << "IT2: " << it2 << '\n';
    return pfx[col][it2] - pfx[col][it];
}
vector <vector <ll>> dp;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N;
    m = M;
    fish.resize(N+1);
    pfx.resize(N+1);
    for (int i = 0; i < M; i++) {
        fish[X[i] + 1].push_back({Y[i] + 1, W[i]});
    }
    // dp = vector <vector <ll>> (N+1, vector <ll> (N+1, -1));
    for (int i = 1; i <= N; i++) {
        fish[i].push_back({0, 0});
        sort(fish[i].begin(), fish[i].end());
        pfx[i].resize((int)fish[i].size() + 5, 1e18);
        for (int j = 1; j < (int)fish[i].size(); j++)
            pfx[i][j] = pfx[i][j-1] + fish[i][j].second;
    }
    ll ans = max(get_sum(1, N+1, 1), get_sum(1, N+1, 2));
    for (int i = 1; i <= N; i++) {
        if (N > 2)
            ans = max(ans, get_sum(1, i, 1) + get_sum(i+1, N, 2));
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18112 KB Output is correct
2 Correct 48 ms 20912 KB Output is correct
3 Correct 20 ms 14424 KB Output is correct
4 Correct 12 ms 14424 KB Output is correct
5 Incorrect 94 ms 34984 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 0 ms 344 KB Output is correct
2 Correct 64 ms 23416 KB Output is correct
3 Correct 75 ms 27316 KB Output is correct
4 Correct 36 ms 18156 KB Output is correct
5 Correct 42 ms 20928 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 13 ms 14428 KB Output is correct
11 Correct 13 ms 14428 KB Output is correct
12 Correct 37 ms 18324 KB Output is correct
13 Correct 43 ms 20932 KB Output is correct
14 Correct 45 ms 18292 KB Output is correct
15 Correct 44 ms 20172 KB Output is correct
16 Correct 52 ms 18112 KB Output is correct
17 Correct 42 ms 20156 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14428 KB Output is correct
2 Incorrect 12 ms 14324 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 0 ms 348 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 0 ms 348 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 0 ms 348 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 13 ms 14428 KB Output is correct
2 Incorrect 12 ms 14324 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 36 ms 18112 KB Output is correct
2 Correct 48 ms 20912 KB Output is correct
3 Correct 20 ms 14424 KB Output is correct
4 Correct 12 ms 14424 KB Output is correct
5 Incorrect 94 ms 34984 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '0'
6 Halted 0 ms 0 KB -