SHARE
TWEET

Untitled

a guest Nov 19th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <ctime>
  5. #include <random>
  6.  
  7. int MOD_INT = 123456789;
  8.  
  9. using std::cout;
  10. using std::cin;
  11. using std::vector;
  12.  
  13. template <typename Type>
  14. class AllSegments {
  15.   vector<Type> values;
  16.   vector<vector<Type>> table;
  17.  
  18.   void updateSegment(size_t start, size_t length);
  19.   void updateLength(size_t length);
  20.  
  21. public:
  22.   explicit AllSegments(const vector<Type>& input);
  23.   Type getTotalAmountOfTree();
  24.   void getTable();
  25. };
  26.  
  27. template <typename Type> // to correct
  28. void AllSegments<Type>::updateSegment(size_t start, size_t length) { // start + length <= size
  29.   Type answer = 0;
  30.   for (size_t pivot = 0; pivot < length; ++pivot) {
  31.     if (pivot == 0 || values[start + pivot - 1] != values[start + pivot]) {
  32.       answer += table[start][start + pivot] *
  33.                 table[start + pivot + 1][start + length] % MOD_INT;
  34.       answer = answer % MOD_INT;
  35.     }
  36.   }
  37.   table[start][start + length] = answer;
  38. }
  39.  
  40. template <typename Type>
  41. void AllSegments<Type>::updateLength(size_t length) {
  42.   if (length == 0) {
  43.     for (size_t iter = 0; iter < values.size() + 1; ++iter) {
  44.       table[iter][iter] = 1;
  45.     }
  46.     return;
  47.   }
  48.   for (size_t start = 0; start + length <= values.size(); ++start) {
  49.     updateSegment(start, length);
  50.   }
  51. }
  52.  
  53. template <typename Type>
  54. AllSegments<Type>::AllSegments(const vector<Type>& input) {
  55.   values = input;
  56.   size_t size = values.size();
  57.   vector <Type> empty_str(size + 1, 0);
  58.   for (size_t iter = 0; iter < size + 1; ++iter) {
  59.     table.push_back(empty_str);
  60.   }
  61.   for (size_t length = 0; length < size + 1; ++length) {
  62.     updateLength(length);
  63.   }
  64. }
  65.  
  66. template <typename Type>
  67. Type AllSegments<Type>::getTotalAmountOfTree() {
  68.   return table[0][values.size()];
  69. }
  70.  
  71. template <typename Type>
  72. void AllSegments<Type>::getTable() {
  73.   size_t size = table.size();
  74.   for (size_t start = 0; start < size; ++start) {
  75.     for (size_t end = 0; end < size; ++end) {
  76.       cout << table[start][end] << " ";
  77.     }
  78.     cout << "\n";
  79.   }
  80. }
  81.  
  82. vector<long long int> readInput(size_t& size) {
  83.   cin >> size;
  84.   long long int current;
  85.   vector<long long int> answer;
  86.   answer.reserve(size);
  87.   for (size_t iter = 0; iter < size; ++iter) {
  88.     cin >> current;
  89.     answer.push_back(current);
  90.   }
  91.   return answer;
  92. }
  93.  
  94. /*vector<size_t> randomInput(size_t& size) {
  95.   std::mt19937 gen;
  96.   gen.seed(static_cast<unsigned int>(time(0)));
  97.   size = 500;
  98.   size_t current;
  99.   vector<size_t> answer;
  100.   answer.reserve(size);
  101.   for (size_t iter = 0; iter < size; ++iter) {
  102.     current = gen() % 70;
  103.     answer.push_back(current);
  104.     // cout << current << " ";
  105.   }
  106.   cout << "\n";
  107.   return answer;
  108. }*/
  109.  
  110. int main() {
  111.   size_t size;
  112.   vector<long long int> values;
  113.   values = readInput(size);
  114.   // values = randomInput(size);
  115.   std::sort(values.begin(), values.end());
  116.   AllSegments<long long int> solution = AllSegments<long long int >(values);
  117.   cout << solution.getTotalAmountOfTree() << "\n";
  118.   return 0;
  119. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top