ocean #6314(2008/05/21 22:38 GMT) [ C++ ] Rating0/0=0.00
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
#include <iostream> #include <vector> #include <algorithm> #include <cassert> typedef unsigned long ulong; template <typename T> void sort_and_unique(std::vector<T>& v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); } int main() { size_t N; ulong M; assert(std::cin); std::cin >> N >> M; assert(1 <= N && N <= 1000); assert(1 <= M && M <= 200000000); // allows 1 throw std::vector<ulong> s1(1, 0); // 0 point == no throw s1.reserve(N + 1); for (size_t i = 0; i < N; ++i) { ulong p; assert(std::cin); std::cin >> p; assert(1 <= p && p <= 100000000); if (p <= M) { s1.push_back(p); } } sort_and_unique(s1); // allows 2 throw std::vector<ulong> s2; s2.reserve(s1.size() * s1.size()); for (size_t i = 0; i < s1.size(); ++i) { for (size_t j = 0; j < s1.size() && s1[i] + s1[j] <= M; ++j) { s2.push_back(s1[i] + s1[j]); } } sort_and_unique(s2); // allows 4 throw ulong max_point = 0; std::vector<ulong>::reverse_iterator rit = s2.rbegin(); for (std::vector<ulong>::iterator it = s2.begin(); it != s2.end(); ++it) { while (rit != s2.rend() && *it + *rit > M) { ++rit; } if (rit == s2.rend()) { break; } max_point = std::max(max_point, *it + *rit); } std::cout << max_point << std::endl; }
Rating0/0=0.00-0+
[ reply ]
ocean
#6314()
[
C++
]
Rating0/0=0.00
Rating0/0=0.00-0+
[ reply ]