답안 #632653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632653	2022-08-20T14:01:27 Z	stefanlin	메기 농장 (IOI22_fish)	C++17	컴파일 오류	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;
}

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

    // result
    long long result = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < dp_left[i].size(); ++j) {
            result = std::max(dp_left[i][j].second + dp_right[i][j].second, result);
        }
    }

    return result;
}

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 '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:93: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]
   93 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:94: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]
   94 |             for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:106: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]
  106 |         for (int j = 0; j < dp_right[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:107: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]
  107 |             for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:120: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]
  120 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:121:83: error: no matching function for call to 'max(long int, long long int&)'
  121 |             result = std::max(dp_left[i][j].second + dp_right[i][j].second, result);
      |                                                                                   ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from fish.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
fish.cpp:121:83: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
  121 |             result = std::max(dp_left[i][j].second + dp_right[i][j].second, result);
      |                                                                                   ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from fish.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
fish.cpp:121:83: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
  121 |             result = std::max(dp_left[i][j].second + dp_right[i][j].second, result);
      |                                                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from fish.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
fish.cpp:121:83: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
  121 |             result = std::max(dp_left[i][j].second + dp_right[i][j].second, result);
      |                                                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from fish.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
fish.cpp:121:83: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
  121 |             result = std::max(dp_left[i][j].second + dp_right[i][j].second, result);
      |                                                                                   ^
fish.cpp: In function 'int main()':
fish.cpp:139: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]
  139 |         for (int j = 1; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:147: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]
  147 |         for (int j = 0; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:158: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]
  158 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:159: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]
  159 |             for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:171: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]
  171 |         for (int j = 0; j < dp_right[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:172: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]
  172 |             for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:187: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]
  187 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~