oj.uz

Submission #1065918

# Submission time Handle Problem Language Result Execution time Memory
1065918 2024-08-19T13:07:34 Z j_vdd16 Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 81452 KB 
#include "fish.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

vvii fishes;
int weightSum(int x, int y1, int y2) {
    if (x >= fishes.size() || y2 <= y1)
        return 0;

    int res = 0;
    for (auto [y, w] : fishes[x]) {
        if (y1 <= y && y < y2)
            res += w;
    }

    return res;
}

long long max_weights(signed N, signed M, vector<signed> X, std::vector<signed> Y, std::vector<signed> W) {
    fishes = vvii(N);
    loop(i, M) {
        fishes[X[i]].push_back({Y[i], W[i]});
    }
    fishes.push_back({});

    loop(x, N) {
        sort(all(fishes[x]));
    }

    vector<map<int, int>> beforeDp(N);
    vector<map<int, int>> bothDp(N);

    //bestBefore, bestBeforeAndAfter
    loop(x, N) {
        if (x == 0) {
            for (auto [y, w] : fishes[x + 1]) {
                bothDp[0][y + 1] = weightSum(x + 1, 0, y + 1);
            }
            beforeDp[0][0] = 0;

            continue;
        }

        set<int> heights;
        for (auto [y, w] : fishes[x - 1]) {
            heights.insert(y + 1);
        }
        for (auto [y, w] : fishes[x + 1]) {
            heights.insert(y + 1);
        }
        heights.insert(0);

        int bestBefore2 = 0;
        int bestBoth3 = 0;
        if (x >= 2) {
            for (auto [prevY, prevScore] : beforeDp[x - 2])
                bestBefore2 = max(bestBefore2, prevScore);
        }
        if (x >= 3) {
            for (auto [prevY, prevScore] : bothDp[x - 3])
                bestBoth3 = max(bestBoth3, prevScore);
        }

        for (int height : heights) {
            int& both = bothDp[x][height];
            int& before = beforeDp[x][height];

            for (auto [prevHeight, prevScore] : beforeDp[x - 1]) {
                int prevCur = weightSum(x - 1, prevHeight, height);

                both = max(both, prevScore + prevCur);
                before = max(before, prevScore + prevCur);
            }
            for (auto [prevY, prevScore] : bothDp[x - 1]) {
                if (prevY <= height) 
                    continue;

                int prevCur = -weightSum(x, 0, height);
                both = max(both, prevScore + prevCur);
            }

            int prevWeight = weightSum(x - 1, 0, height);
            both = max(both, bestBefore2 + prevWeight);
            both = max(both, bestBoth3 + prevWeight);

            before = max(before, bestBefore2 + prevWeight);
            before = max(before, bestBoth3 + prevWeight);
            
            int nextWeight = weightSum(x + 1, 0, height);
            both += nextWeight;
        }
    }

    int res = 0;
    loop(x, N) {
        for (auto [y, score] : beforeDp[x]) {
            res = max(res, score);
        }
        for (auto [y, score] : bothDp[x]) {
            res = max(res, score);
        }
    }

    return res;
}

Compilation message

fish.cpp: In function 'long long int weightSum(long long int, long long int, long long int)':
fish.cpp:35:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if (x >= fishes.size() || y2 <= y1)
      |         ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1089 ms 18280 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24600 KB Output is correct
2 Correct 22 ms 24628 KB Output is correct
3 Correct 44 ms 32388 KB Output is correct
4 Correct 40 ms 31532 KB Output is correct
5 Correct 110 ms 42540 KB Output is correct
6 Correct 66 ms 42540 KB Output is correct
7 Correct 68 ms 42540 KB Output is correct
8 Correct 86 ms 42644 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 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 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 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 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 13 ms 748 KB Output is correct
17 Execution timed out 1100 ms 4744 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 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 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 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 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 13 ms 748 KB Output is correct
17 Execution timed out 1100 ms 4744 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24600 KB Output is correct
2 Correct 22 ms 24628 KB Output is correct
3 Correct 44 ms 32388 KB Output is correct
4 Correct 40 ms 31532 KB Output is correct
5 Correct 110 ms 42540 KB Output is correct
6 Correct 66 ms 42540 KB Output is correct
7 Correct 68 ms 42540 KB Output is correct
8 Correct 86 ms 42644 KB Output is correct
9 Correct 100 ms 55080 KB Output is correct
10 Correct 61 ms 29884 KB Output is correct
11 Correct 126 ms 59432 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 24 ms 24544 KB Output is correct
19 Correct 23 ms 24628 KB Output is correct
20 Correct 22 ms 24628 KB Output is correct
21 Correct 22 ms 24628 KB Output is correct
22 Correct 111 ms 54552 KB Output is correct
23 Correct 187 ms 77500 KB Output is correct
24 Correct 194 ms 81452 KB Output is correct

Subtask #8
0 / 16.0

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