Submission #670040

#	Time	Username	Problem	Language	Result	Execution time	Memory
670040		CatalinT	Catfish Farm (IOI22_fish)	C++17	18 / 100	120 ms	22216 KiB

fish

#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <bitset>
 
using namespace std;

using int64 = long long;



int64 max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector<int64> sum_cols(N + 2);
    vector<vector<pair<int, int>>> vec_cols(N + 2);

    for (int i = 0; i < M; i++)
        X[i]++;

    for (int i = 0; i < M; i++) {
        sum_cols[X[i]] += W[i];
        vec_cols[X[i]].emplace_back(Y[i], W[i]);
    }

    for (int i = 0; i <= N + 1; i++) {
        sort(vec_cols[i].begin(), vec_cols[i].end());
    }

    vector<int64> dp(N + 2, 0);

    for (int i = 2; i <= N + 1; i++) {
        dp[i] = dp[i-1];

        // i - 2 ... i, take [i-2], [i]
        dp[i] = max(dp[i], (i - 3 >= 0 ? dp[i - 3] : 0) + sum_cols[i-2] + sum_cols[i]);
    
        // i - 4 ... i, take [i-4], [i-2], [i]
        if (i - 4 >= 0) {
            dp[i] = max(dp[i],
                (i - 5 >= 0 ? dp[i - 5] : 0) + sum_cols[i-4] + sum_cols[i-2] + sum_cols[i]);           
        }

        // i - 3 .. i
        if (i - 3 >= 0) {
            int64 prev = (i - 4 >= 0 ? dp[i - 4] : 0); 
            // Take all of [i], [i-3]
            dp[i] = max(dp[i], prev + sum_cols[i] + sum_cols[i-3]);
        
            auto build_stair = [&] (int a, int b, int f) {
                int64 tmp = prev + sum_cols[f];

                // adj on a
                // building over b


                int at = -1;

                int64 gained = 0;
                int64 lost = sum_cols[b];

                int64 res = tmp + gained + lost;

                int idx = 0;

                for (auto el : vec_cols[a]) {
                    gained += el.second;
                    // lost
                    while (idx < vec_cols[b].size() && vec_cols[b][idx].first <= el.first) {
                        lost -= vec_cols[b][idx].second;
                        idx++;
                    }

                    res = max(res, tmp + gained + lost);
                }

                return res;
            };

            dp[i] = max(dp[i], build_stair(i - 3, i - 2, i));
            dp[i] = max(dp[i], build_stair(i, i - 1, i - 3));
        }
    }

    return dp[N + 1];
}

// int main() {
//     // cerr << max_weights(
//     //     5, 
//     //     4,
//     //     vector<int>{0, 1, 4, 3},
//     //     vector<int>{2, 1, 4, 3},
//     //     vector<int>{5, 2, 1, 3}
//     // ) << "\n";
//     // cerr << max_weights(
//     //     4, 
//     //     4,
//     //     vector<int>{3, 0, 1, 2},
//     //     vector<int>{3, 0, 2, 2},
//     //     vector<int>{100, 50, 1000, 10}
//     // ) << "\n";
//     return 0;
// }

Compilation message (stderr)

fish.cpp: In lambda function:
fish.cpp:83:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |                     while (idx < vec_cols[b].size() && vec_cols[b][idx].first <= el.first) {
      |                            ~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:71:21: warning: unused variable 'at' [-Wunused-variable]
   71 |                 int at = -1;
      |                     ^~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16