fork(3) download
copy 
  1. #include <iostream>
  2.  
  3. template <int Mod>
  4. struct ModuloArithmetic {
  5. 	static int add(int x, int y) {
  6. 		long long const tmp = static_cast<long long>(x) + y;
  7. 		return (tmp > Mod) ? (tmp - Mod) : tmp;
  8. 	}
  9.  
  10. 	static int mul(int x, int y) {
  11. 		long long const tmp = static_cast<long long>(x) * y;
  12. 		return tmp % Mod;
  13. 	}
  14. };
  15.  
  16. using Modulo = ModuloArithmetic<1000000000 + 7>;
  17.  
  18. struct Column {
  19. 	int h;
  20. 	int h_partial;
  21. 	int partial;
  22.  
  23. 	static Column Next(int h, Column const &prev) {
  24. 		int const h_partial = std::min(prev.h, h);
  25. 		int const h_partial_from_prev = std::min(prev.h_partial, h_partial);
  26. 		int const ones = h_partial - h_partial_from_prev + 1;
  27. 		int const fat = Modulo::mul(prev.partial, h_partial_from_prev);
  28. 		int const partial = Modulo::add(ones, fat);
  29. 		return {h, h_partial, partial};
  30. 	}
  31.  
  32. 	int Total() const {
  33. 		return Modulo::add(Modulo::mul(h_partial, partial), (h - h_partial));
  34. 	}
  35. };
  36.  
  37. int main() {
  38. 	std::cin.sync_with_stdio(false);
  39. 	int n;
  40. 	std::cin >> n;
  41.  
  42. 	int possibilities = 0;
  43. 	Column prev{0, 0, 0};
  44. 	for (int i = 0; i < n; ++i) {
  45. 		int h;
  46. 		std::cin >> h;
  47. 		Column const next = Column::Next(h - 1, prev);
  48. 		//std::cout << next.h << " " << next.h_partial << " " << next.partial << "\n";
  49. 		possibilities = Modulo::add(possibilities, next.Total());
  50. 		prev = next;
  51. 	}
  52. 	std::cout << possibilities;
  53. 	return 0;
  54. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
3 4 2
stdout
copy 
13
https://ideone.com/Th3Kkq
language:
C++14 (gcc 8.3)
created:
6 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!