Submission #632655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
632655	2022-08-20T14:02:22 Z	stefanlin	Catfish Farm (IOI22_fish)	C++17	Compilation error	0 ms	0 KB

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;
}

int 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
    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);
                }
                dp_left[i][j].second = std::max(dp_left[i - 1][k].second + add_weight, dp_left[i][j].second);
            }
        }
    }

    // right
    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);
                }
                dp_right[i][j].second = std::max(dp_right[i + 1][k].second + add_weight, dp_right[i][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

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 'int main()':
fish.cpp:79: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]
   79 |         for (int j = 1; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:87: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]
   87 |         for (int j = 0; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:98: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]
   98 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:99: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]
   99 |             for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:111: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]
  111 |         for (int j = 0; j < dp_right[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:112: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]
  112 |             for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:127: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]
  127 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccBQdA5I.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cctRBQMJ.o:fish.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccBQdA5I.o: in function `main':
grader.cpp:(.text.startup+0x25e): undefined reference to `max_weights(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status