제출 #632656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632656		stefanlin	Catfish Farm (IOI22_fish)	C++17	3 / 100	1048 ms	47328 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
    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
    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
    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;
}

컴파일 시 표준 에러 (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: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: In function 'int test_main()':
fish.cpp:141: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]
  141 |         for (int j = 1; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:149: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]
  149 |         for (int j = 0; j < weight[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
fish.cpp:160: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]
  160 |         for (int j = 0; j < dp_left[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:161: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]
  161 |             for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:173: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]
  173 |         for (int j = 0; j < dp_right[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:174: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]
  174 |             for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:189: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]
  189 |         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