oj.uz

Submission #1065983

# Submission time Handle Problem Language Result Execution time Memory
1065983 2024-08-19T13:51:56 Z j_vdd16 Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 146300 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 (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];

        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 124 ms 51840 KB Output is correct
2 Correct 161 ms 59712 KB Output is correct
3 Correct 25 ms 37172 KB Output is correct
4 Correct 26 ms 37424 KB Output is correct
5 Correct 618 ms 146300 KB Output is correct
6 Correct 355 ms 145704 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 1093 ms 47572 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 37232 KB Output is correct
2 Correct 26 ms 37172 KB Output is correct
3 Correct 53 ms 47124 KB Output is correct
4 Correct 45 ms 46472 KB Output is correct
5 Correct 92 ms 61480 KB Output is correct
6 Correct 76 ms 61476 KB Output is correct
7 Correct 88 ms 61480 KB Output is correct
8 Correct 91 ms 61484 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 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 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 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 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 344 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 1 ms 600 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 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 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 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 10 ms 860 KB Output is correct
17 Correct 719 ms 12372 KB Output is correct
18 Correct 712 ms 12084 KB Output is correct
19 Correct 439 ms 12116 KB Output is correct
20 Correct 329 ms 11256 KB Output is correct
21 Correct 331 ms 11404 KB Output is correct
22 Execution timed out 1081 ms 20144 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 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 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 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 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 10 ms 860 KB Output is correct
17 Correct 719 ms 12372 KB Output is correct
18 Correct 712 ms 12084 KB Output is correct
19 Correct 439 ms 12116 KB Output is correct
20 Correct 329 ms 11256 KB Output is correct
21 Correct 331 ms 11404 KB Output is correct
22 Execution timed out 1081 ms 20144 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 37232 KB Output is correct
2 Correct 26 ms 37172 KB Output is correct
3 Correct 53 ms 47124 KB Output is correct
4 Correct 45 ms 46472 KB Output is correct
5 Correct 92 ms 61480 KB Output is correct
6 Correct 76 ms 61476 KB Output is correct
7 Correct 88 ms 61480 KB Output is correct
8 Correct 91 ms 61484 KB Output is correct
9 Correct 124 ms 74016 KB Output is correct
10 Correct 66 ms 42312 KB Output is correct
11 Correct 148 ms 84520 KB Output is correct
12 Correct 0 ms 344 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 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 30 ms 37020 KB Output is correct
19 Correct 28 ms 36992 KB Output is correct
20 Correct 33 ms 37172 KB Output is correct
21 Correct 33 ms 37428 KB Output is correct
22 Correct 118 ms 73444 KB Output is correct
23 Correct 189 ms 102696 KB Output is correct
24 Correct 194 ms 106536 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 51840 KB Output is correct
2 Correct 161 ms 59712 KB Output is correct
3 Correct 25 ms 37172 KB Output is correct
4 Correct 26 ms 37424 KB Output is correct
5 Correct 618 ms 146300 KB Output is correct
6 Correct 355 ms 145704 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Execution timed out 1093 ms 47572 KB Time limit exceeded
9 Halted 0 ms 0 KB -