oj.uz

Submission #1065975

# Submission time Handle Problem Language Result Execution time Memory
1065975 2024-08-19T13:46:28 Z j_vdd16 Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 152704 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() || 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 + 1);
    loop(x, N + 1) {
        sort(all(fishes[x]));

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

            prefixWeight[x][y] = total;
        }
    }

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

    vi maxBefore(N);
    vi maxBoth(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);
                maxBoth[x] = max(maxBoth[x], bothDp[0][y + 1]);
            }
            beforeDp[0][0] = 0;
            maxBefore[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);

        //cout << "Size: " << heights.size() << endl;

        int bestBefore2 = 0;
        int bestBoth3 = 0;
        if (x >= 2) {
            bestBefore2 = maxBefore[x - 2];
        }
        if (x >= 3) {
            bestBoth3 = maxBoth[x - 3];
        }

        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;

            maxBefore[x] = max(maxBefore[x], before);
            maxBoth[x] = max(maxBoth[x], both);
        }


        int& both = bothDp[x][0];
        int& before = beforeDp[x][0];

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

            both = max(both, prevScore);
        }

        both = max(both, bestBefore2);
        both = max(both, bestBoth3);

        before = max(before, bestBefore2);
        before = max(before, bestBoth3);

        maxBefore[x] = max(maxBefore[x], before);
        maxBoth[x] = max(maxBoth[x], both);
    }

    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() || y2 <= y1)
      |         ~~^~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 53036 KB Output is correct
2 Correct 155 ms 61588 KB Output is correct
3 Correct 27 ms 37164 KB Output is correct
4 Correct 30 ms 37080 KB Output is correct
5 Correct 639 ms 152704 KB Output is correct
6 Correct 366 ms 152108 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37228 KB Output is correct
2 Correct 28 ms 37152 KB Output is correct
3 Correct 57 ms 47876 KB Output is correct
4 Correct 46 ms 47096 KB Output is correct
5 Correct 78 ms 63000 KB Output is correct
6 Correct 76 ms 62252 KB Output is correct
7 Correct 83 ms 62868 KB Output is correct
8 Correct 87 ms 62872 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 432 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 348 KB Output is correct
6 Correct 0 ms 344 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 1116 KB Output is correct
11 Correct 2 ms 856 KB Output is correct
12 Correct 2 ms 860 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 432 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 348 KB Output is correct
6 Correct 0 ms 344 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 1116 KB Output is correct
11 Correct 2 ms 856 KB Output is correct
12 Correct 2 ms 860 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 10 ms 860 KB Output is correct
17 Correct 730 ms 13140 KB Output is correct
18 Correct 695 ms 12840 KB Output is correct
19 Correct 421 ms 12940 KB Output is correct
20 Correct 340 ms 11952 KB Output is correct
21 Correct 332 ms 11944 KB Output is correct
22 Execution timed out 1033 ms 21328 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 432 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 348 KB Output is correct
6 Correct 0 ms 344 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 1116 KB Output is correct
11 Correct 2 ms 856 KB Output is correct
12 Correct 2 ms 860 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 10 ms 860 KB Output is correct
17 Correct 730 ms 13140 KB Output is correct
18 Correct 695 ms 12840 KB Output is correct
19 Correct 421 ms 12940 KB Output is correct
20 Correct 340 ms 11952 KB Output is correct
21 Correct 332 ms 11944 KB Output is correct
22 Execution timed out 1033 ms 21328 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37228 KB Output is correct
2 Correct 28 ms 37152 KB Output is correct
3 Correct 57 ms 47876 KB Output is correct
4 Correct 46 ms 47096 KB Output is correct
5 Correct 78 ms 63000 KB Output is correct
6 Correct 76 ms 62252 KB Output is correct
7 Correct 83 ms 62868 KB Output is correct
8 Correct 87 ms 62872 KB Output is correct
9 Correct 106 ms 75308 KB Output is correct
10 Correct 68 ms 44220 KB Output is correct
11 Correct 154 ms 88128 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 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 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 31 ms 37160 KB Output is correct
19 Correct 26 ms 37172 KB Output is correct
20 Correct 26 ms 37172 KB Output is correct
21 Correct 29 ms 36964 KB Output is correct
22 Correct 118 ms 75564 KB Output is correct
23 Correct 210 ms 106020 KB Output is correct
24 Correct 205 ms 110620 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 53036 KB Output is correct
2 Correct 155 ms 61588 KB Output is correct
3 Correct 27 ms 37164 KB Output is correct
4 Correct 30 ms 37080 KB Output is correct
5 Correct 639 ms 152704 KB Output is correct
6 Correct 366 ms 152108 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Execution timed out 1026 ms 50464 KB Time limit exceeded
9 Halted 0 ms 0 KB -