oj.uz

Submission #1066013

# Submission time Handle Problem Language Result Execution time Memory
1066013 2024-08-19T14:09:15 Z j_vdd16 Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 151528 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);
            
            int nextWeight = weightSum(x + 1, 0, height);
            both += nextWeight;

            maxBefore[x] = max(maxBefore[x], before);
            maxBoth[x] = max(maxBoth[x], both);
        }
        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);
            
            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];

        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 137 ms 53264 KB Output is correct
2 Correct 153 ms 61332 KB Output is correct
3 Correct 28 ms 37160 KB Output is correct
4 Correct 26 ms 37164 KB Output is correct
5 Correct 575 ms 151528 KB Output is correct
6 Correct 363 ms 150572 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 1058 ms 49456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 37348 KB Output is correct
2 Correct 28 ms 37168 KB Output is correct
3 Correct 60 ms 47628 KB Output is correct
4 Correct 53 ms 47148 KB Output is correct
5 Correct 87 ms 63020 KB Output is correct
6 Correct 81 ms 62248 KB Output is correct
7 Correct 90 ms 63016 KB Output is correct
8 Correct 86 ms 62876 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 1168 KB Output is correct
11 Correct 1 ms 604 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 604 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 1168 KB Output is correct
11 Correct 1 ms 604 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 604 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 10 ms 1100 KB Output is correct
17 Correct 766 ms 13256 KB Output is correct
18 Correct 754 ms 12736 KB Output is correct
19 Correct 410 ms 12980 KB Output is correct
20 Correct 340 ms 12112 KB Output is correct
21 Correct 328 ms 11860 KB Output is correct
22 Execution timed out 1041 ms 21208 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 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 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 1168 KB Output is correct
11 Correct 1 ms 604 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 604 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 10 ms 1100 KB Output is correct
17 Correct 766 ms 13256 KB Output is correct
18 Correct 754 ms 12736 KB Output is correct
19 Correct 410 ms 12980 KB Output is correct
20 Correct 340 ms 12112 KB Output is correct
21 Correct 328 ms 11860 KB Output is correct
22 Execution timed out 1041 ms 21208 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 37348 KB Output is correct
2 Correct 28 ms 37168 KB Output is correct
3 Correct 60 ms 47628 KB Output is correct
4 Correct 53 ms 47148 KB Output is correct
5 Correct 87 ms 63020 KB Output is correct
6 Correct 81 ms 62248 KB Output is correct
7 Correct 90 ms 63016 KB Output is correct
8 Correct 86 ms 62876 KB Output is correct
9 Correct 102 ms 75308 KB Output is correct
10 Correct 69 ms 44224 KB Output is correct
11 Correct 149 ms 88104 KB Output is correct
12 Correct 0 ms 432 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 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 26 ms 37224 KB Output is correct
19 Correct 28 ms 37024 KB Output is correct
20 Correct 26 ms 37172 KB Output is correct
21 Correct 26 ms 37168 KB Output is correct
22 Correct 117 ms 75564 KB Output is correct
23 Correct 195 ms 106044 KB Output is correct
24 Correct 207 ms 110632 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 53264 KB Output is correct
2 Correct 153 ms 61332 KB Output is correct
3 Correct 28 ms 37160 KB Output is correct
4 Correct 26 ms 37164 KB Output is correct
5 Correct 575 ms 151528 KB Output is correct
6 Correct 363 ms 150572 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Execution timed out 1058 ms 49456 KB Time limit exceeded
9 Halted 0 ms 0 KB -