Submission #632672

#	Time	Username	Problem	Language	Result	Execution time	Memory
632672		stefanlin	Catfish Farm (IOI22_fish)	C++17	3 / 100	1085 ms	44796 KiB

fish

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <limits>
#include <cstring>

#define NN 100005

std::vector<std::pair<int, int64_t>> weight[NN];
std::vector<std::pair<int, int64_t>> dp_left[NN];
std::vector<std::pair<int, int64_t>> dp_right[NN];

void printWeight(int n, int m) {
    for (int i = 0; i < n; ++i) {
        std::cout << i << " -> ";
        for (int j = 0; j < weight[i].size(); ++j) {
            std::cout << "(" << weight[i][j].first << ", " << weight[i][j].second << ") ";
        }
        std::cout << std::endl;
    }
}

void printDp(int n, int m) {
    std::cout << "======= dp_left =======" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cout << i << " -> ";
        for (int j = 0; j < dp_left[i].size(); ++j) {
            std::cout << "(" << dp_left[i][j].first << ", " << dp_left[i][j].second << ") ";
        }
        std::cout << std::endl;
    }
    std::cout << "======= dp_right =======" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cout << i << " -> ";
        for (int j = 0; j < dp_right[i].size(); ++j) {
            std::cout << "(" << dp_right[i][j].first << ", " << dp_right[i][j].second << ") ";
        }
        std::cout << std::endl;
    }
}

int64_t binarySearchWeight(int i, int h) {
    if (weight[i].size() == 0) {
        return 0;
    }

    auto iter = std::upper_bound(weight[i].begin(), weight[i].end(), std::make_pair(h, std::numeric_limits<int64_t>::max()));
    if (iter == weight[i].begin()) {
        return 0;
    }
    --iter;
    return iter->second;
}

void printBinarySearchResult() {
    int64_t ret;
    ret = binarySearchWeight(3, 2);
    std::cout << "binary search (3, 2) -> " << ret << std::endl;

    ret = binarySearchWeight(3, 3);
    std::cout << "binary search (3, 3) -> " << ret << std::endl;

    ret = binarySearchWeight(3, 4);
    std::cout << "binary search (3, 4) -> " << ret << std::endl;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    int n = N, m = M;
    for (int i = 0; i < m; ++i) {
        weight[X[i]].push_back(std::make_pair(Y[i], W[i]));
    }

    for (int i = 0; i < n; ++i) {
        std::sort(weight[i].begin(), weight[i].end());
        // 计算前缀和
        for (int j = 1; j < weight[i].size(); ++j) {
            weight[i][j].second += weight[i][j - 1].second;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < weight[i].size(); ++j) {
            int h = weight[i][j].first - 1;
            dp_left[i].push_back(std::make_pair(h, 0));
            dp_right[i].push_back(std::make_pair(h, 0));
        }
        dp_left[i].push_back(std::make_pair(n - 1, 0));
        dp_right[i].push_back(std::make_pair(n - 1, 0));
    }

    // left
    int64_t temp = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < dp_left[i].size(); ++j) {
            for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
                int64_t add_weight = 0;
                if (dp_left[i - 1][k].first < dp_left[i][j].first) {
                    add_weight = binarySearchWeight(i - 1, dp_left[i][j].first) - binarySearchWeight(i - 1, dp_left[i - 1][k].first);
                } else {
                    if (temp > dp_left[i][j].second) {
                        dp_left[i][j].second = temp;
                    }
                    break;
                }
                dp_left[i][j].second = std::max(dp_left[i - 1][k].second + add_weight, dp_left[i][j].second);
            }
        }
        temp = 0;
        for (int j = 0; j < dp_left[i].size(); ++j) {
            temp = std::max(temp, dp_left[i][j].second);
        }
    }

    // right
    temp = 0;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < dp_right[i].size(); ++j) {
            for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
                int64_t add_weight = 0;
                if (dp_right[i + 1][k].first < dp_right[i][j].first) {
                    add_weight = binarySearchWeight(i + 1, dp_right[i][j].first) - binarySearchWeight(i + 1, dp_right[i + 1][k].first);
                } else {
                    if (temp > dp_right[i][j].second) {
                        dp_right[i][j].second = temp;
                    }
                    break;
                }
                dp_right[i][j].second = std::max(dp_right[i + 1][k].second + add_weight, dp_right[i][j].second);
            }
        }
        temp = 0;
        for (int j = 0; j < dp_right[i].size(); ++j) {
            temp = std::max(temp, dp_right[i][j].second);
        }
    }

    // result
    int64_t result = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < dp_left[i].size(); ++j) {
            if (dp_left[i][j].second + dp_right[i][j].second > result) {
                result = dp_left[i][j].second + dp_right[i][j].second;
            }
        }
    }

    return result;
}

int test_main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, w;
        std::cin >> x >> y >> w;
        weight[x].push_back(std::make_pair(y, w));
    }
    for (int i = 0; i < n; ++i) {
        std::sort(weight[i].begin(), weight[i].end());
        // 计算前缀和
        for (int j = 1; j < weight[i].size(); ++j) {
            weight[i][j].second += weight[i][j - 1].second;
        }
    }
    // printWeight(n, m);
    // printBinarySearchResult();

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < weight[i].size(); ++j) {
            int h = weight[i][j].first - 1;
            dp_left[i].push_back(std::make_pair(h, 0));
            dp_right[i].push_back(std::make_pair(h, 0));
        }
        dp_left[i].push_back(std::make_pair(n - 1, 0));
        dp_right[i].push_back(std::make_pair(n - 1, 0));
    }

    // left
    int64_t temp = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < dp_left[i].size(); ++j) {
            for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
                int64_t add_weight = 0;
                if (dp_left[i - 1][k].first < dp_left[i][j].first) {
                    add_weight = binarySearchWeight(i - 1, dp_left[i][j].first) - binarySearchWeight(i - 1, dp_left[i - 1][k].first);
                } else {
                    if (dp_left[i][j].second >= temp) {
                        break;
                    }
                }
                dp_left[i][j].second = std::max(dp_left[i - 1][k].second + add_weight, dp_left[i][j].second);
            }
        }
        temp = 0;
        for (int j = 0; j < dp_left[i - 1].size() && i > 0; ++j) {
            temp = std::max(temp, dp_left[i - 1][j].second);
        }
    }

    // right
    temp = 0;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < dp_right[i].size(); ++j) {
            for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
                int64_t add_weight = 0;
                if (dp_right[i + 1][k].first < dp_right[i][j].first) {
                    add_weight = binarySearchWeight(i + 1, dp_right[i][j].first) - binarySearchWeight(i + 1, dp_right[i + 1][k].first);
                } else {
                    if (dp_right[i][j].second >= temp) {
                        break;
                    }
                }
                dp_right[i][j].second = std::max(dp_right[i + 1][k].second + add_weight, dp_right[i][j].second);
            }
        }
        temp = 0;
        for (int j = 0; j < dp_left[i + 1].size() && i < n - 1; ++j) {
            temp = std::max(temp, dp_left[i + 1][j].second);
        }
    }

    // printDp(n, m);

    // result
    int64_t result = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < dp_left[i].size(); ++j) {
            if (dp_left[i][j].second + dp_right[i][j].second > result) {
                result = dp_left[i][j].second + dp_right[i][j].second;
            }
        }
    }
    std::cout << result << std::endl;
    return 0;
}

Compilation message (stderr)

fish.cpp: In function 'void printWeight(int, int)':
fish.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for (int j = 0; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'void printDp(int, int)':
fish.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int j = 0; j < dp_right[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int j = 1; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int j = 0; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:95:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for (int j = 0; j < dp_right[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:118:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (int j = 0; j < dp_right[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:140:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp: In function 'int test_main()':
fish.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         for (int j = 1; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:169:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for (int j = 0; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:181:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:182:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |             for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:195:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |         for (int j = 0; j < dp_left[i - 1].size() && i > 0; ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:203:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |         for (int j = 0; j < dp_right[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:204:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |             for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:217:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |         for (int j = 0; j < dp_left[i + 1].size() && i < n - 1; ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:227:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~

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