oj.uz

Submission #1065912

# Submission time Handle Problem Language Result Execution time Memory
1065912 2024-08-19T13:03:06 Z j_vdd16 Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 85544 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];

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

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

                int prevCur = -weightSum(x, 0, min(prevY, height));

                both = max(both, prevScore + prevCur + nextWeight);
                //before = max(before, prevScore + prevCur);
            }

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

            before = max(before, bestBefore2 + weightSum(x - 1, 0, height));
            before = max(before, bestBoth3 + weightSum(x - 1, 0, height));
        }
    }

    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 19584 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 344 KB Output is correct
2 Execution timed out 1097 ms 21072 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24624 KB Output is correct
2 Correct 25 ms 24616 KB Output is correct
3 Correct 47 ms 33300 KB Output is correct
4 Correct 41 ms 32300 KB Output is correct
5 Correct 79 ms 44332 KB Output is correct
6 Correct 69 ms 43564 KB Output is correct
7 Correct 72 ms 44072 KB Output is correct
8 Correct 88 ms 44164 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 1 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 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 2 ms 604 KB Output is correct
13 Correct 0 ms 348 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 1 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 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 2 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 584 KB Output is correct
16 Correct 14 ms 872 KB Output is correct
17 Execution timed out 1080 ms 5520 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 1 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 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 2 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 584 KB Output is correct
16 Correct 14 ms 872 KB Output is correct
17 Execution timed out 1080 ms 5520 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24624 KB Output is correct
2 Correct 25 ms 24616 KB Output is correct
3 Correct 47 ms 33300 KB Output is correct
4 Correct 41 ms 32300 KB Output is correct
5 Correct 79 ms 44332 KB Output is correct
6 Correct 69 ms 43564 KB Output is correct
7 Correct 72 ms 44072 KB Output is correct
8 Correct 88 ms 44164 KB Output is correct
9 Correct 100 ms 56440 KB Output is correct
10 Correct 59 ms 31676 KB Output is correct
11 Correct 135 ms 63012 KB Output is correct
12 Correct 0 ms 348 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 22 ms 24540 KB Output is correct
19 Correct 25 ms 24628 KB Output is correct
20 Correct 24 ms 24512 KB Output is correct
21 Correct 23 ms 24628 KB Output is correct
22 Correct 108 ms 56728 KB Output is correct
23 Correct 189 ms 80936 KB Output is correct
24 Correct 195 ms 85544 KB Output is correct

Subtask #8
0 / 16.0

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