fork download
copy 
  1. #include <set>
  2. #include <array>
  3. #include <limits>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <sstream>
  8. #include <numeric>
  9. #include <tuple>
  10. #include <cassert>
  11. #include <unordered_set>
  12. #include <bitset>
  13. #include <thread>
  14. #include <future>
  15. #include <memory>
  16. #include <map>
  17. #include <unordered_map>
  18.  
  19. namespace
  20. {
  21.     namespace common
  22.     {
  23.         template<class Func>
  24.         void repeat_n(int size, Func func)
  25.         {
  26.             for(int i=0 ; i < size; ++i)
  27.             {
  28.                 func(i);
  29.             }
  30.         }
  31.  
  32.         template<class T>
  33.         T get(std::istream& stream)
  34.         {
  35.             T value;
  36.             stream >> value;
  37.             return value;
  38.         }
  39.  
  40.         template<class Func>
  41.         void run_test_case(std::istream& stream, Func func)
  42.         {
  43.             repeat_n(get<int>(stream), [func, &stream](int )
  44.             {
  45.                 func(stream);
  46.             });
  47.         }
  48.  
  49.  
  50.         template<class T>
  51.         struct optional
  52.         {
  53.         public:
  54.             optional() = default;
  55.             optional(T value_) : _value(value_), _has_value(true)
  56.             {
  57.  
  58.             }
  59.  
  60.             bool has_value() const
  61.             {
  62.                 return _has_value;
  63.             }
  64.  
  65.             const T& value() const
  66.             {
  67.                 return _value;
  68.             }
  69.  
  70.         private:
  71.             bool _has_value = false;
  72.             T _value;
  73.         };
  74.  
  75.  
  76.         template<class Def>
  77.         class memoization
  78.         {
  79.  
  80.             using key_type = typename Def::key_type;
  81.             using value_type = typename Def::value_type;
  82.             using this_type = memoization<Def>;
  83.             using solve_func = std::function<value_type (const key_type&, this_type&)>;
  84.  
  85.         public:
  86.             memoization(solve_func func) : _func(func)
  87.             {
  88.             }
  89.  
  90.             value_type solve(const key_type& key)
  91.             {
  92.                 auto optional_value = Def::get(_map, key);
  93.                 if(optional_value.has_value())
  94.                 {
  95.                     return optional_value.value();
  96.                 }
  97.                 else
  98.                 {
  99.                     auto value = _func(key, *this);
  100.                     return Def::set(_map, key, value);
  101.                 }
  102.             }
  103.  
  104.         private:
  105.             solve_func _func;
  106.             typename Def::map_type _map;
  107.         };
  108.     }
  109.  
  110.     struct map_def
  111.     {
  112.         using map_type = std::unordered_map<int, int>;
  113.         using key_type = std::pair<short, short>;
  114.         using value_type = int;
  115.  
  116.         union id_type
  117.         {
  118.             struct
  119.             {
  120.                 short k1;
  121.                 short k2;
  122.             }raw;
  123.             int value;
  124.         } ;
  125.  
  126.         static common::optional<int> get(const map_type& map_, key_type key)
  127.         {
  128.  
  129.  
  130.             id_type id;
  131.             id.raw.k1 = key.first;
  132.             id.raw.k2 = key.second;
  133.  
  134.  
  135.             auto find_value = map_.find(id.value);
  136.  
  137.             if(find_value != map_.end())
  138.             {
  139.                 return common::optional<int>(find_value->second);
  140.             }
  141.             return common::optional<int>();
  142.         }
  143.  
  144.         static value_type set(map_type& map_, key_type key, int value)
  145.         {
  146.             id_type id;
  147.  
  148.             id.raw.k1 = key.first;
  149.             id.raw.k2 = key.second;
  150.  
  151.             map_[id.value] = value;
  152.             return value;
  153.         }
  154.     };
  155.  
  156.     class triangle_path_data
  157.     {
  158.     public:
  159.         static const int max_size = 100;
  160.  
  161.         triangle_path_data() = default;
  162.  
  163.  
  164.         int size() const
  165.         {
  166.             return _size;
  167.         }
  168.  
  169.         static triangle_path_data create_from_stream(std::istream& stream)
  170.         {
  171.             triangle_path_data triangle_path_data_;
  172.             triangle_path_data_._size = common::get<int>(stream);
  173.  
  174.             common::repeat_n(triangle_path_data_._size, [&](int row_index)
  175.             {
  176.                 common::repeat_n(row_index+1, [&](int column_index)
  177.                 {
  178.                     triangle_path_data_._data[row_index][column_index] = common::get<int>(stream);
  179.                 });
  180.             });
  181.  
  182.             return triangle_path_data_;
  183.         }
  184.  
  185.         int get(int row, int column)
  186.         {
  187.             assert(is_valid(row, column));
  188.             return _data[row][column];
  189.         }
  190.  
  191.         bool is_valid(int row, int column)
  192.         {
  193.             return row < _size && column <= row;
  194.         }
  195.  
  196.     private:
  197.         int _size =0;
  198.         std::array<std::array<int, 100>, 100> _data;
  199.     };
  200.  
  201.     struct triangle_path_solver
  202.     {
  203.     public:
  204.         triangle_path_solver(triangle_path_data& data_) : triangle_data_(data_){}
  205.  
  206.         int solve(const map_def::key_type& key, common::memoization<map_def>& memo) const
  207.         {
  208.             if(triangle_data_.is_valid(key.first, key.second) == false)
  209.             {
  210.                 return 0;
  211.             }
  212.             else
  213.             {
  214.                 return triangle_data_.get(key.first, key.second) +
  215.                        std::max(memo.solve(std::make_pair(key.first+1, key.second)), memo.solve(std::make_pair(key.first+1, key.second+1)));
  216.             }
  217.         }
  218.  
  219.     private:
  220.         triangle_path_data& triangle_data_;
  221.     };
  222. }
  223.  
  224.  
  225. #ifdef __TEST__
  226. int triangle_path_main()
  227. #else
  228. int main()
  229. #endif
  230. {
  231.     common::run_test_case(std::cin, [](std::istream& stream)
  232.     {
  233.         auto triangle_data_ = triangle_path_data::create_from_stream(stream);
  234.  
  235.         triangle_path_solver solver(triangle_data_);
  236.  
  237.         common::memoization<map_def> memoization_solver([solver](const map_def::key_type& key, common::memoization<map_def>& memo )
  238.                                                         {
  239.                                                             return solver.solve(key, memo);
  240.                                                         });
  241.  
  242.         std::cout << memoization_solver.solve(std::make_pair(0,0)) << std::endl;
  243.     });
  244.     return 0;
  245. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
2
5
6
1  2
3  7  4
9  4  1  7
2  7  5  9  4
5
1
2 4
8 16 8
32 64 32 64
128 256 128 256 128
stdout
copy 
28
341
https://ideone.com/EFetuw
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!