oj.uz

Submission #1065978

# Submission time Handle Problem Language Result Execution time Memory
1065978 2024-08-19T13:49:05 Z j_vdd16 Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 146268 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]);
        before = max(both, maxBefore[x - 1]);
        // 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 118 ms 51836 KB Output is correct
2 Correct 150 ms 59800 KB Output is correct
3 Correct 30 ms 37172 KB Output is correct
4 Correct 26 ms 37172 KB Output is correct
5 Correct 620 ms 146268 KB Output is correct
6 Correct 364 ms 145192 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 1085 ms 47612 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 37160 KB Output is correct
2 Correct 30 ms 37168 KB Output is correct
3 Correct 54 ms 46904 KB Output is correct
4 Correct 46 ms 46376 KB Output is correct
5 Correct 77 ms 61484 KB Output is correct
6 Correct 83 ms 61484 KB Output is correct
7 Correct 82 ms 61476 KB Output is correct
8 Correct 78 ms 61476 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 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 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 1 ms 580 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 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 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 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 1 ms 580 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 1 ms 604 KB Output is correct
16 Correct 10 ms 860 KB Output is correct
17 Correct 716 ms 12432 KB Output is correct
18 Correct 714 ms 12112 KB Output is correct
19 Correct 430 ms 12116 KB Output is correct
20 Correct 329 ms 11344 KB Output is correct
21 Correct 319 ms 11088 KB Output is correct
22 Execution timed out 1047 ms 19828 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 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 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 1 ms 580 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 1 ms 604 KB Output is correct
16 Correct 10 ms 860 KB Output is correct
17 Correct 716 ms 12432 KB Output is correct
18 Correct 714 ms 12112 KB Output is correct
19 Correct 430 ms 12116 KB Output is correct
20 Correct 329 ms 11344 KB Output is correct
21 Correct 319 ms 11088 KB Output is correct
22 Execution timed out 1047 ms 19828 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 37160 KB Output is correct
2 Correct 30 ms 37168 KB Output is correct
3 Correct 54 ms 46904 KB Output is correct
4 Correct 46 ms 46376 KB Output is correct
5 Correct 77 ms 61484 KB Output is correct
6 Correct 83 ms 61484 KB Output is correct
7 Correct 82 ms 61476 KB Output is correct
8 Correct 78 ms 61476 KB Output is correct
9 Correct 102 ms 73832 KB Output is correct
10 Correct 70 ms 42500 KB Output is correct
11 Correct 152 ms 84520 KB Output is correct
12 Correct 1 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 26 ms 37072 KB Output is correct
19 Correct 27 ms 37164 KB Output is correct
20 Correct 27 ms 36996 KB Output is correct
21 Correct 29 ms 37160 KB Output is correct
22 Correct 116 ms 73260 KB Output is correct
23 Correct 215 ms 102696 KB Output is correct
24 Correct 203 ms 106416 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 51836 KB Output is correct
2 Correct 150 ms 59800 KB Output is correct
3 Correct 30 ms 37172 KB Output is correct
4 Correct 26 ms 37172 KB Output is correct
5 Correct 620 ms 146268 KB Output is correct
6 Correct 364 ms 145192 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1085 ms 47612 KB Time limit exceeded
9 Halted 0 ms 0 KB -