oj.uz

Submission #627697

# Submission time Handle Problem Language Result Execution time Memory
627697 2022-08-12T18:56:56 Z tutis Catfish Farm (IOI22_fish) C++17
0 / 100
 827 ms 2097152 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    vector<pair<int, ll>>P[N];
    for (int i = 0; i < M; i++)
        P[X[i]].push_back({Y[i], W[i]});
    for (int i = 0; i < N; i++)
        sort(P[i].begin(), P[i].end());
    for (int i = 0; i < N; i++)
    {
        P[i].push_back({N, 0});
        for (int j = 1; j < (int)P[i].size(); j++)
            P[i][j].second += P[i][j - 1].second;
    }
    int ret = 0;
    ll dp[N];
    ll u[N][N];
    ll d[N][N];
    ll u1[N][N];
    ll d1[N][N];
    auto get = [&](int x, int y)->ll
    {
        if (x < 0 || x >= N)
            return 0;
        auto it = lower_bound(P[x].begin(), P[x].end(), make_pair(y + 1, -1ll));
        if (it == P[x].begin())
            return 0;
        it--;
        return it->second;
    };
    for (int x = 0; x < N; x++)
    {
        dp[x] = 0;
        for (int y = 0; y < N; y++)
        {
            u[x][y] = d[x][y] = 0;
            u1[x][y] = u[x][y] - get(x, y);
            d1[x][y] = d[x][y] + get(x + 1, y);
        }
        for (int y = 1; y < N; y++)
            u1[x][y] = max(u1[x][y], u1[x][y - 1]);
        for (int y = N - 2; y > 0; y--)
            d1[x][y] = max(d1[x][y], d1[x][y - 1]);
        ll sum = 0;
        int i = 0;
        if (x == 0)
            continue;
        for (int y = 0; y < N; y++)
        {
            u[x][y] = dp[x - 1];
            u[x][y] = max(u[x][y], get(x - 1, y) + (x - 2 >= 0 ? dp[x - 2] : 0ll));
            u[x][y] -= get(x - 1, y);
            u[x][y] = max(u[x][y], u1[x - 1][y]);
            u[x][y] += get(x - 1, y);
        }
        for (int y = 0; y < N; y++)
            u1[x][y] = u[x][y] - get(x, y);
        d[x][N - 1] = u[x][N - 1];
        for (int y = N - 1; y >= 0; y--)
        {
            d[x][y] += get(x, y);
            d[x][y] = max(d[x][y], d1[x - 1][y]);
            d[x][y] -= get(x, y);
        }
        for (int y = N - 1; y >= 0; y--)
            d1[x][y] = d[x][y] + get(x + 1, y);
        for (int y = 1; y < N; y++)
            u1[x][y] = max(u1[x][y], u1[x][y - 1]);
        for (int y = N - 2; y > 0; y--)
            d1[x][y] = max(d1[x][y], d1[x][y - 1]);
        dp[x] = dp[x - 1];
        dp[x] = max(dp[x], get(x, N - 1) + u[x - 1][N - 1]);
        dp[x] = max(dp[x], u[x][N - 1]);
        for (int y = 0; y < N; y++)
        {
            dp[x] = max(dp[x], d1[x - 1][y]);
            dp[x] = max(dp[x], d[x][y]);
        }
    }
    return dp[N - 1];
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:48:12: warning: unused variable 'sum' [-Wunused-variable]
   48 |         ll sum = 0;
      |            ^~~
fish.cpp:49:13: warning: unused variable 'i' [-Wunused-variable]
   49 |         int i = 0;
      |             ^
fish.cpp:19:9: warning: unused variable 'ret' [-Wunused-variable]
   19 |     int ret = 0;
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 827 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 757 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 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 Runtime error 757 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 827 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -