oj.uz

Submission #632656

# Submission time Handle Problem Language Result Execution time Memory
632656 2022-08-20T14:03:18 Z stefanlin Catfish Farm (IOI22_fish) C++17
3 / 100
 1000 ms 47328 KB 
#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;
}

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: 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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 20540 KB Output is correct
2 Correct 67 ms 22468 KB Output is correct
3 Correct 16 ms 13524 KB Output is correct
4 Correct 19 ms 13652 KB Output is correct
5 Correct 189 ms 43780 KB Output is correct
6 Correct 186 ms 47328 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7256 KB Output is correct
2 Execution timed out 1048 ms 28484 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13552 KB Output is correct
2 Correct 18 ms 13520 KB Output is correct
3 Incorrect 46 ms 18260 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7256 KB Output is correct
2 Correct 5 ms 7344 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7260 KB Output is correct
8 Correct 5 ms 7260 KB Output is correct
9 Incorrect 5 ms 7388 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '165109154345'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7256 KB Output is correct
2 Correct 5 ms 7344 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7260 KB Output is correct
8 Correct 5 ms 7260 KB Output is correct
9 Incorrect 5 ms 7388 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '165109154345'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7256 KB Output is correct
2 Correct 5 ms 7344 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7260 KB Output is correct
8 Correct 5 ms 7260 KB Output is correct
9 Incorrect 5 ms 7388 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '165109154345'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13552 KB Output is correct
2 Correct 18 ms 13520 KB Output is correct
3 Incorrect 46 ms 18260 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 20540 KB Output is correct
2 Correct 67 ms 22468 KB Output is correct
3 Correct 16 ms 13524 KB Output is correct
4 Correct 19 ms 13652 KB Output is correct
5 Correct 189 ms 43780 KB Output is correct
6 Correct 186 ms 47328 KB Output is correct
7 Correct 4 ms 7256 KB Output is correct
8 Execution timed out 1048 ms 28484 KB Time limit exceeded
9 Halted 0 ms 0 KB -