oj.uz

Submission #1075105

# Submission time Handle Problem Language Result Execution time Memory
1075105 2024-08-25T18:26:03 Z Zicrus Catfish Farm (IOI22_fish) C++17
23 / 100
 189 ms 63624 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) {
    ll res = 0;
    for (int k = 0; k < f[i].size(); k++) {
        if (f[i][k].first < j) res += f[i][k].second;
    }
    return res;
}
    
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;
    int q = 4;
    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].resize(q+1);
        sort(f[i].begin(), f[i].end());
        sort(relH[i].begin(), relH[i].end());
    }

    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(q+1, vector<ll>(q+1)));
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= q; j++) {
            for (int j1 = 0; j1 <= q; j1++) {
                for (int k = 0; k <= q; 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 <= q; j++) {
        for (int j1 = 0; j1 <= q; j1++) {
            res = max(res, dp[n-1][j][j1]);
        }
    }
    for (int i = n-2; i >= n-5 && i >= 0; i--) {
        for (int j = 0; j <= q; j++) {
            for (int j1 = 0; j1 <= q; j1++) {
                ll val = dp[i][j][j1] + sum(i+1, relH[i][j]);
                res = max(res, val);
            }
        }
    }
    return res;
}
    
#ifdef TEST
#include "grader.cpp"
#endif

Compilation message

fish.cpp: In function 'll sum(int, int)':
fish.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int k = 0; k < f[i].size(); k++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 46420 KB Output is correct
2 Correct 70 ms 46612 KB Output is correct
3 Correct 91 ms 46416 KB Output is correct
4 Correct 89 ms 49492 KB Output is correct
5 Correct 119 ms 54868 KB Output is correct
6 Correct 124 ms 54084 KB Output is correct
7 Correct 130 ms 54868 KB Output is correct
8 Correct 119 ms 54776 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 46420 KB Output is correct
2 Correct 70 ms 46612 KB Output is correct
3 Correct 91 ms 46416 KB Output is correct
4 Correct 89 ms 49492 KB Output is correct
5 Correct 119 ms 54868 KB Output is correct
6 Correct 124 ms 54084 KB Output is correct
7 Correct 130 ms 54868 KB Output is correct
8 Correct 119 ms 54776 KB Output is correct
9 Correct 121 ms 54464 KB Output is correct
10 Correct 82 ms 31828 KB Output is correct
11 Correct 172 ms 63172 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 67 ms 46428 KB Output is correct
19 Correct 68 ms 46428 KB Output is correct
20 Correct 60 ms 46416 KB Output is correct
21 Correct 72 ms 46416 KB Output is correct
22 Correct 134 ms 54356 KB Output is correct
23 Correct 178 ms 63056 KB Output is correct
24 Correct 189 ms 63624 KB Output is correct

Subtask #8
0 / 16.0

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