#include <iostream> #include <fstream> #include <vector> #include <limits> #include <algorithm> int n; struct Cost { int a, b; int c; bool used; }; std::vector<Cost> costs; void read(std::istream & str) { Cost c; str >> n; costs.reserve((n*n)/2 + n); for(int i=0 ; i < n ; ++i) { for(int x=0 ; x < n-i ; ++x) { c.a = i; c.b = i + x; c.used = false; str >> c.c; costs.push_back(c); } } } void calc() { long sum = 0; int size = 0; std::sort(costs.begin(), costs.end(), [](const Cost & c1, const Cost & c2)->bool{return c1.c < c2.c;}); for(int in = 0 ; in < n ; ++in) { for(size_t i=0 ; i<costs.size() ; ++i) { Cost & c = costs[i]; if( c.a <= in && c.b >= in ) { if( !c.used ) { size += 1; c.used = true; sum += c.c; } break; } } } for(size_t i=0 ; i<costs.size() && size < n ; ++i) { Cost & c = costs[i]; if( !c.used ) { size += 1; sum += c.c; c.used = true; } } std::cout << sum << std::endl; } int main() { std::cin.sync_with_stdio(false); read(std::cin); calc(); return 0; }
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 93 94 95 96 97 98 99 | #include <iostream> #include <fstream> #include <vector> #include <limits> #include <algorithm> int n; struct Cost { int a, b; int c; bool used; }; std::vector<Cost> costs; void read(std::istream & str) { Cost c; str >> n; costs.reserve((n*n)/2 + n); for(int i=0 ; i < n ; ++i) { for(int x=0 ; x < n-i ; ++x) { c.a = i; c.b = i + x; c.used = false; str >> c.c; costs.push_back(c); } } } void calc() { long sum = 0; int size = 0; std::sort(costs.begin(), costs.end(), [](const Cost & c1, const Cost & c2)->bool{return c1.c < c2.c;}); for(int in = 0 ; in < n ; ++in) { for(size_t i=0 ; i<costs.size() ; ++i) { Cost & c = costs[i]; if( c.a <= in && c.b >= in ) { if( !c.used ) { size += 1; c.used = true; sum += c.c; } break; } } } for(size_t i=0 ; i<costs.size() && size < n ; ++i) { Cost & c = costs[i]; if( !c.used ) { size += 1; sum += c.c; c.used = true; } } std::cout << sum << std::endl; } int main() { std::cin.sync_with_stdio(false); read(std::cin); calc(); return 0; } |