oj.uz

Submission #1066023

# Submission time Handle Problem Language Result Execution time Memory
1066023 2024-08-19T14:12:21 Z j_vdd16 Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 150316 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);
        // }
        
        int bestBefore2 = 0;
        int bestBoth3 = 0;
        if (x >= 2) {
            bestBefore2 = maxBefore[x - 2];
        }
        if (x >= 3) {
            bestBoth3 = maxBoth[x - 3];
        }

        for (auto [y, w] : fishes[x - 1]) {
            int height = y + 1;
            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);
            
            maxBefore[x] = max(maxBefore[x], before);
        }
        for (auto [y, w] : fishes[x + 1]) {
            int height = y + 1;
            if (heights.count(height)) continue;

            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);
            
            

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

        for (auto [height, score] : bothDp[x]) {
            int nextWeight = weightSum(x + 1, 0, height);
            bothDp[x][height] += nextWeight;
            
            maxBoth[x] = max(maxBoth[x], bothDp[x][height]);
        }

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

        both = max({both, maxBefore[x - 1], bestBefore2, bestBoth3});
        before = max(before, both);

        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 136 ms 52844 KB Output is correct
2 Correct 166 ms 61076 KB Output is correct
3 Correct 26 ms 37172 KB Output is correct
4 Correct 26 ms 37168 KB Output is correct
5 Correct 700 ms 150316 KB Output is correct
6 Correct 352 ms 149284 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 1087 ms 49584 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 37220 KB Output is correct
2 Correct 29 ms 37168 KB Output is correct
3 Correct 55 ms 47632 KB Output is correct
4 Correct 51 ms 47124 KB Output is correct
5 Correct 81 ms 63016 KB Output is correct
6 Correct 76 ms 62220 KB Output is correct
7 Correct 78 ms 62820 KB Output is correct
8 Correct 79 ms 63020 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 428 KB Output is correct
5 Correct 0 ms 600 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 1116 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 428 KB Output is correct
5 Correct 0 ms 600 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 1116 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 11 ms 872 KB Output is correct
17 Correct 791 ms 13396 KB Output is correct
18 Correct 747 ms 12736 KB Output is correct
19 Correct 433 ms 13056 KB Output is correct
20 Correct 349 ms 12112 KB Output is correct
21 Correct 347 ms 11776 KB Output is correct
22 Execution timed out 1047 ms 20816 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 428 KB Output is correct
5 Correct 0 ms 600 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 1116 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 11 ms 872 KB Output is correct
17 Correct 791 ms 13396 KB Output is correct
18 Correct 747 ms 12736 KB Output is correct
19 Correct 433 ms 13056 KB Output is correct
20 Correct 349 ms 12112 KB Output is correct
21 Correct 347 ms 11776 KB Output is correct
22 Execution timed out 1047 ms 20816 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 37220 KB Output is correct
2 Correct 29 ms 37168 KB Output is correct
3 Correct 55 ms 47632 KB Output is correct
4 Correct 51 ms 47124 KB Output is correct
5 Correct 81 ms 63016 KB Output is correct
6 Correct 76 ms 62220 KB Output is correct
7 Correct 78 ms 62820 KB Output is correct
8 Correct 79 ms 63020 KB Output is correct
9 Correct 104 ms 75172 KB Output is correct
10 Correct 72 ms 44216 KB Output is correct
11 Correct 187 ms 88104 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 27 ms 37172 KB Output is correct
19 Correct 31 ms 37056 KB Output is correct
20 Correct 29 ms 37160 KB Output is correct
21 Correct 30 ms 37048 KB Output is correct
22 Correct 126 ms 75504 KB Output is correct
23 Correct 260 ms 106276 KB Output is correct
24 Correct 229 ms 110632 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 52844 KB Output is correct
2 Correct 166 ms 61076 KB Output is correct
3 Correct 26 ms 37172 KB Output is correct
4 Correct 26 ms 37168 KB Output is correct
5 Correct 700 ms 150316 KB Output is correct
6 Correct 352 ms 149284 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1087 ms 49584 KB Time limit exceeded
9 Halted 0 ms 0 KB -