oj.uz

Submission #673004

# Submission time Handle Problem Language Result Execution time Memory
673004 2022-12-19T11:07:59 Z pls33 Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 2097152 KB 
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion

void update(int64_t val, p32 fish, vvi64 &vect)
{
    vect[fish.first][fish.second] = max(vect[fish.first][fish.second], val);
}

int64_t weight_sum(int i, int j, vvi64 &prefix, int row)
{
    if (i == -1)
    {
        return 0;
    }

    int64_t sum = prefix[row][j];
    if (i)
    {
        sum -= prefix[row][i - 1];
    }

    return sum;
}

int64_t new_weight(p32 lhs, p32 rhs, vvi64 &prefix){
    long left = rhs.first > 0
                        ? weight_sum(0, rhs.second, prefix, rhs.first - 1)
                        : 0;

    long right = (rhs.first + 1 < (int)prefix.size())
                        ? weight_sum(0, rhs.second, prefix, rhs.first + 1)
                        : 0;

    if (lhs.first == -1)
    {
        return left + right;
    }

    if (rhs.first - lhs.first > 2)
    {
        return left + right;
    }

    if (rhs.first - lhs.first == 2)
    {
        if (lhs.second >= rhs.second)
        {
            return right;
        }

        left -= weight_sum(0, lhs.second, prefix, rhs.first - 1);

        return left + right;
    }

    if (lhs.second > rhs.second)
    {
        left = -weight_sum(0, rhs.second, prefix, rhs.first);
        return left + right;
    }

    left -= weight_sum(0, lhs.second, prefix, rhs.first) +
            weight_sum(0, lhs.second, prefix, rhs.first - 1);
    return left + right;
}

long long max_weights(int N, int M,
                      std::vector<int> X,
                      std::vector<int> Y,
                      std::vector<int> W)
{
    vp32 fish;
    vvi64 prefix(N, vi64(N));
    for (int i = 0; i < M; i++)
    {
        prefix[X[i]][Y[i]] = W[i];

        if (X[i])
        {
            fish.push_back({X[i] - 1, Y[i]});
        }
        if (X[i] < N - 1)
        {
            fish.push_back({X[i] + 1, Y[i]});
        }
    }

    for (auto &row : prefix)
    {
        for (int i = 1; i < (int)row.size(); i++)
        {
            row[i] += row[i - 1];
        }
    }

    sort(fish.begin(), fish.end());
    auto it = unique(fish.begin(), fish.end());
    fish.erase(it, fish.end());

    vvi64 decrease(N, vi64(N));
    vvi64 increase(N, vi64(N));

    for (auto &f : fish)
    {
        int64_t initial = new_weight(p32(-1, -1), f, prefix);
        update(initial, f, increase);
        update(initial, f, decrease);

        for(int i = 0; i < f.first; i++){
            for (int j = 0; j < N; j++)
            {
                int64_t prev = new_weight(p32(i, j), f, prefix);

                if(i == f.first - 1){
                    if(j < f.second){
                        update(prev + increase[i][j], f, increase);
                    }
                    else {
                        update(prev + decrease[i][j], f, decrease);
                    }
                }
                else {
                    prev += max(increase[i][j], decrease[i][j]);
                    update(prev, f, increase);
                    update(prev, f, decrease);
                }
            }
            
        }
    }

    int64_t res = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            res = max({res, increase[i][j], decrease[i][j]});
        }
    }
    return res;
}

Compilation message

fish.cpp:4: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    4 | #pragma region dalykai
      | 
fish.cpp:27: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   27 | #pragma endregion
      |

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 834 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 36 ms 852 KB Output is correct
10 Correct 645 ms 2564 KB Output is correct
11 Correct 62 ms 852 KB Output is correct
12 Correct 463 ms 2500 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 303 ms 2488 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 36 ms 852 KB Output is correct
10 Correct 645 ms 2564 KB Output is correct
11 Correct 62 ms 852 KB Output is correct
12 Correct 463 ms 2500 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 303 ms 2488 KB Output is correct
15 Correct 144 ms 2388 KB Output is correct
16 Correct 46 ms 540 KB Output is correct
17 Execution timed out 1072 ms 5024 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 36 ms 852 KB Output is correct
10 Correct 645 ms 2564 KB Output is correct
11 Correct 62 ms 852 KB Output is correct
12 Correct 463 ms 2500 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 303 ms 2488 KB Output is correct
15 Correct 144 ms 2388 KB Output is correct
16 Correct 46 ms 540 KB Output is correct
17 Execution timed out 1072 ms 5024 KB Time limit exceeded
18 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 Execution timed out 1150 ms 2031896 KB Time limit exceeded
2 Halted 0 ms 0 KB -