oj.uz

Submission #1065946

# Submission time Handle Problem Language Result Execution time Memory
1065946 2024-08-19T13:25:22 Z j_vdd16 Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 151168 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;
vector<map<int, int>> prefixWeight;

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

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

    // return res;

    auto it1 = prefixWeight[x].upper_bound(y2 - 1);
    auto it2 = prefixWeight[x].upper_bound(y1 - 1);
    int res = (--it1)->second - (--it2)->second;
    //cout << x << ' ' << y1 << ' ' << y2 << " = " << res << endl;
    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({});

    prefixWeight = vector<map<int, int>>(N);
    loop(x, N) {
        sort(all(fishes[x]));

        int total = 0;
        prefixWeight[x][-2] = 0;
        for (auto [y, w] : fishes[x]) {
            total += w;

            prefixWeight[x][y] = total;
        }

        //prefixWeight[x][INT_MAX] = 0;
    }

    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:37: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]
   37 |     if (x >= fishes.size() - 1 || y2 <= y1)
      |         ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 50300 KB Output is correct
2 Correct 154 ms 59884 KB Output is correct
3 Correct 31 ms 35636 KB Output is correct
4 Correct 30 ms 35408 KB Output is correct
5 Correct 630 ms 151168 KB Output is correct
6 Correct 386 ms 150324 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35636 KB Output is correct
2 Correct 30 ms 35464 KB Output is correct
3 Correct 65 ms 46612 KB Output is correct
4 Correct 49 ms 45436 KB Output is correct
5 Correct 84 ms 61484 KB Output is correct
6 Correct 84 ms 60888 KB Output is correct
7 Correct 82 ms 61228 KB Output is correct
8 Correct 94 ms 61480 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 1120 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 1 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 1120 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 11 ms 860 KB Output is correct
17 Correct 759 ms 13196 KB Output is correct
18 Correct 744 ms 12684 KB Output is correct
19 Correct 437 ms 12936 KB Output is correct
20 Correct 343 ms 12120 KB Output is correct
21 Correct 330 ms 11928 KB Output is correct
22 Execution timed out 1060 ms 21368 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 1120 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 11 ms 860 KB Output is correct
17 Correct 759 ms 13196 KB Output is correct
18 Correct 744 ms 12684 KB Output is correct
19 Correct 437 ms 12936 KB Output is correct
20 Correct 343 ms 12120 KB Output is correct
21 Correct 330 ms 11928 KB Output is correct
22 Execution timed out 1060 ms 21368 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35636 KB Output is correct
2 Correct 30 ms 35464 KB Output is correct
3 Correct 65 ms 46612 KB Output is correct
4 Correct 49 ms 45436 KB Output is correct
5 Correct 84 ms 61484 KB Output is correct
6 Correct 84 ms 60888 KB Output is correct
7 Correct 82 ms 61228 KB Output is correct
8 Correct 94 ms 61480 KB Output is correct
9 Correct 117 ms 73772 KB Output is correct
10 Correct 87 ms 43328 KB Output is correct
11 Correct 156 ms 86468 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 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 30 ms 35652 KB Output is correct
19 Correct 29 ms 35620 KB Output is correct
20 Correct 29 ms 35636 KB Output is correct
21 Correct 29 ms 35532 KB Output is correct
22 Correct 126 ms 74020 KB Output is correct
23 Correct 211 ms 104500 KB Output is correct
24 Correct 233 ms 108856 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 50300 KB Output is correct
2 Correct 154 ms 59884 KB Output is correct
3 Correct 31 ms 35636 KB Output is correct
4 Correct 30 ms 35408 KB Output is correct
5 Correct 630 ms 151168 KB Output is correct
6 Correct 386 ms 150324 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1092 ms 48888 KB Time limit exceeded
9 Halted 0 ms 0 KB -