oj.uz

Submission #1066063

# Submission time Handle Problem Language Result Execution time Memory
1066063 2024-08-19T14:34:29 Z j_vdd16 Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 130428 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 ll 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;

vector<vector<pair<int, ll>>> fishes;
vector<map<int, ll>> prefixWeight;

inline ll 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);
    ll 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 = vector<vector<pair<int, ll>>>(N);
    loop(i, M) {
        fishes[X[i]].push_back({Y[i], W[i]});
    }
    fishes.push_back({});

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

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

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

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

    vector<ll> maxBefore(N);
    vector<ll> maxBoth(N);

    //bestBefore, bestBeforeAndAfter
    loop(x, N) {
        if (x == 0) {
            for (const 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;
        }

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

        int counter = 0;
        for (const auto& [y, w] : fishes.at(x - 1)) {
            int height = y + 1;
            ll& both = bothDp[x][height];
            ll& before = beforeDp[x][height];

            for (const auto& [prevHeight, prevScore] : beforeDp.at(x - 1)) {
                counter++;
                ll prevCur = weightSum(x - 1, prevHeight, height);

                both = max(both, prevScore + prevCur);
                before = max(before, prevScore + prevCur);
            }
            for (const auto& [prevY, prevScore] : bothDp.at(x - 1)) {
                //counter++;
                if (prevY <= height) 
                    continue;

                ll prevCur = -weightSum(x, 0, height);
                both = max(both, prevScore + prevCur);
            }

            ll 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 (const auto& [y, w] : fishes.at(x + 1)) {
            int height = y + 1;
            ll& both = bothDp[x][height];

            for (const auto& [prevHeight, prevScore] : beforeDp.at(x - 1)) {
                counter++;
                ll prevCur = weightSum(x - 1, prevHeight, height);

                both = max(both, prevScore + prevCur);
            }
            for (const auto& [prevY, prevScore] : bothDp.at(x - 1)) {
                //counter++;
                if (prevY <= height) 
                    continue;

                ll prevCur = -weightSum(x, 0, height);
                both = max(both, prevScore + prevCur);
            }

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

        for (const auto& [height, score] : bothDp.at(x)) {
            counter++;
            ll nextWeight = weightSum(x + 1, 0, height);
            bothDp[x][height] += nextWeight;
            
            maxBoth[x] = max(maxBoth[x], bothDp[x][height]);
        }

        //cout << "Counter: " << counter << endl;

        ll& both = bothDp[x][0];
        ll& 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);
    }

    ll 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(int, int, int)':
fish.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<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 121 ms 53860 KB Output is correct
2 Correct 156 ms 62984 KB Output is correct
3 Correct 26 ms 38232 KB Output is correct
4 Correct 25 ms 37940 KB Output is correct
5 Correct 581 ms 129348 KB Output is correct
6 Correct 300 ms 130428 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 1042 ms 45612 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 38196 KB Output is correct
2 Correct 26 ms 38480 KB Output is correct
3 Correct 73 ms 48144 KB Output is correct
4 Correct 49 ms 48424 KB Output is correct
5 Correct 86 ms 64552 KB Output is correct
6 Correct 77 ms 61992 KB Output is correct
7 Correct 79 ms 64044 KB Output is correct
8 Correct 80 ms 64296 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 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 1116 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 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 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 1116 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 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 12 ms 860 KB Output is correct
17 Correct 953 ms 12404 KB Output is correct
18 Execution timed out 1065 ms 12156 KB Time limit exceeded
19 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 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 1116 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 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 12 ms 860 KB Output is correct
17 Correct 953 ms 12404 KB Output is correct
18 Execution timed out 1065 ms 12156 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38196 KB Output is correct
2 Correct 26 ms 38480 KB Output is correct
3 Correct 73 ms 48144 KB Output is correct
4 Correct 49 ms 48424 KB Output is correct
5 Correct 86 ms 64552 KB Output is correct
6 Correct 77 ms 61992 KB Output is correct
7 Correct 79 ms 64044 KB Output is correct
8 Correct 80 ms 64296 KB Output is correct
9 Correct 113 ms 68656 KB Output is correct
10 Correct 71 ms 43616 KB Output is correct
11 Correct 170 ms 87644 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 436 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 25 ms 37172 KB Output is correct
19 Correct 26 ms 38876 KB Output is correct
20 Correct 25 ms 37924 KB Output is correct
21 Correct 25 ms 37172 KB Output is correct
22 Correct 104 ms 70620 KB Output is correct
23 Correct 174 ms 95916 KB Output is correct
24 Correct 172 ms 97956 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 53860 KB Output is correct
2 Correct 156 ms 62984 KB Output is correct
3 Correct 26 ms 38232 KB Output is correct
4 Correct 25 ms 37940 KB Output is correct
5 Correct 581 ms 129348 KB Output is correct
6 Correct 300 ms 130428 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1042 ms 45612 KB Time limit exceeded
9 Halted 0 ms 0 KB -