oj.uz

Submission #1075126

# Submission time Handle Problem Language Result Execution time Memory
1075126 2024-08-25T18:48:29 Z Zicrus Catfish Farm (IOI22_fish) C++17
23 / 100
 817 ms 2097152 KB 
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
    
typedef long long ll;
    
int n, m;
vector<int> x, y, w;
vector<vector<pair<int, int>>> f; // y, w
vector<vector<int>> relH;

ll sum(int i, int j) {
    int id = lower_bound(f[i].begin(), f[i].end(), pair<int, int>(j, -1)) - f[i].begin();
    return id == 0 ? 0 : f[i][id-1].second;
}
    
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N; m = M; x = X; y = Y; w = W;
    f = vector<vector<pair<int, int>>>(n);
    relH = vector<vector<int>>(n);
    for (int i = 0; i < m; i++) {
        f[x[i]].push_back({y[i], w[i]});
        if (x[i] > 0) relH[x[i]-1].push_back(y[i]+1);
        if (x[i] < n-1) relH[x[i]+1].push_back(y[i]+1);
    }
    for (int i = 0; i < n; i++) {
        relH[i].push_back(0);
        sort(f[i].begin(), f[i].end());
        sort(relH[i].begin(), relH[i].end());
        for (int j = 1; j < f[i].size(); j++) {
            f[i][j].second += f[i][j-1].second;
        }
    }

    vector<vector<vector<ll>>> dp(n);
    for (int j = 0; j < relH[0].size(); j++) {
        dp[0].push_back(vector<ll>(1));
    }
    for (int i = 1; i < n; i++) {
        dp[i] = vector<vector<ll>>(relH[i].size());
        for (int j = 0; j < relH[i].size(); j++) {
            dp[i][j] = vector<ll>(relH[i-1].size());
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < relH[i].size(); j++) {
            for (int j1 = 0; j1 < relH[i-1].size(); j1++) {
                for (int k = 0; k < (i < 2 ? 1 : relH[i-2].size()); k++) {
                    ll val = dp[i-1][j1][k];
                    if (relH[i-1][j1] > relH[i][j]) val += sum(i, relH[i-1][j1]) - sum(i, relH[i][j]);
                    if (relH[i][j] > max(relH[i-1][j1], i < 2 ? 0 : relH[i-2][k])) val += sum(i-1, relH[i][j]) - sum(i-1, max(relH[i-1][j1], i < 2 ? 0 : relH[i-2][k]));
                    dp[i][j][j1] = max(dp[i][j][j1], val);
                }
            }
        }
    }

    ll res = 0;
    for (int j = 0; j < relH[n-1].size(); j++) {
        for (int j1 = 0; j1 < relH[n-2].size(); j1++) {
            res = max(res, dp[n-1][j][j1]);
        }
    }
    return res;
}
    
#ifdef TEST
#include "grader.cpp"
#endif

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int j = 1; j < f[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
fish.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int j = 0; j < relH[0].size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~~
fish.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int j = 0; j < relH[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int j = 0; j < relH[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:47:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for (int j1 = 0; j1 < relH[i-1].size(); j1++) {
      |                              ~~~^~~~~~~~~~~~~~~~~~
fish.cpp:48:35: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   48 |                 for (int k = 0; k < (i < 2 ? 1 : relH[i-2].size()); k++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int j = 0; j < relH[n-1].size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
fish.cpp:60:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int j1 = 0; j1 < relH[n-2].size(); j1++) {
      |                          ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 817 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16732 KB Output is correct
2 Correct 16 ms 16856 KB Output is correct
3 Correct 53 ms 25428 KB Output is correct
4 Correct 37 ms 23896 KB Output is correct
5 Correct 85 ms 36096 KB Output is correct
6 Correct 79 ms 35408 KB Output is correct
7 Correct 83 ms 35788 KB Output is correct
8 Correct 84 ms 36112 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16732 KB Output is correct
2 Correct 16 ms 16856 KB Output is correct
3 Correct 53 ms 25428 KB Output is correct
4 Correct 37 ms 23896 KB Output is correct
5 Correct 85 ms 36096 KB Output is correct
6 Correct 79 ms 35408 KB Output is correct
7 Correct 83 ms 35788 KB Output is correct
8 Correct 84 ms 36112 KB Output is correct
9 Correct 96 ms 35664 KB Output is correct
10 Correct 100 ms 31628 KB Output is correct
11 Correct 211 ms 63052 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 428 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 18 ms 16668 KB Output is correct
19 Correct 17 ms 16644 KB Output is correct
20 Correct 17 ms 16732 KB Output is correct
21 Correct 17 ms 16732 KB Output is correct
22 Correct 106 ms 37404 KB Output is correct
23 Correct 262 ms 63120 KB Output is correct
24 Correct 237 ms 63824 KB Output is correct

Subtask #8
0 / 16.0

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