oj.uz

Submission #1074239

# Submission time Handle Problem Language Result Execution time Memory
1074239 2024-08-25T09:00:05 Z zsombor Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 22388 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, m, ans = 0;
vector<vector<pair<int, ll> > > f(2e5);
vector<vector<ll> > dp(2e5);

void get_dp(int i, int j) {
    ll h0, h = f[i][j].first - 1, val = 0, nxt = 0;
    for (auto p: f[i - 1]) if (p.first <= h) val += p.second;
    for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
    dp[i][j] = val;
    for (int k = 0; k < f[i - 1].size(); k++) {
        h0 = f[i - 1][k].first - 1;
        while (h0 >= f[i][nxt].first) val -= f[i][nxt++].second;
        dp[i][j] = max(dp[i][j], dp[i - 1][k] + val);
        if (f[i - 1][k].first <= h) val -= f[i - 1][k].second;
    }
    ans = max(ans, dp[i][j]);
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N;
    m = M;
    for (int i = 0; i < m; i++) {
        X[i]++;
        Y[i]++;
        f[X[i]].push_back({Y[i], W[i]});
    }
    f[0].push_back({1, 0});
    for (int i = 0; i <= n + 1; i++) {
        f[i].push_back({n + 1, 0});
        sort(f[i].begin(), f[i].end());
    }
    dp[0] = {0ll, ll(-1e18)};
    for (int i = 1; i <= n; i++) {
        dp[i].resize(f[i].size(), 0);
        for (int j = 0; j < f[i].size(); j++) get_dp(i, j);
    }
    return ans;
}

Compilation message

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 17612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Execution timed out 1053 ms 22388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15932 KB Output is correct
2 Correct 14 ms 15964 KB Output is correct
3 Incorrect 33 ms 18524 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 3 ms 9836 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Incorrect 4 ms 9820 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 3 ms 9836 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Incorrect 4 ms 9820 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 3 ms 9836 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Incorrect 4 ms 9820 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15932 KB Output is correct
2 Correct 14 ms 15964 KB Output is correct
3 Incorrect 33 ms 18524 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 17612 KB Time limit exceeded
2 Halted 0 ms 0 KB -