fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template <typename T> bool maximize(T &res, const T &val){if(res < val) return res = val, true; return false;}
  6. template <typename T> bool minimize(T &res, const T &val){if(res > val) return res = val, true; return false;}
  7.  
  8. #define ll long long
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  13. #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
  14. #define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
  15. #define C make_pair
  16. #define MASK(i) (1LL << (i))
  17. #define TURN_ON(i, x) ((x) | MASK(i))
  18. #define TURN_OFF(i, x) ((x) & ~MASK(i))
  19. #define RE(i, x) ((x) ^ MASK(i))
  20.  
  21. const ll mod = 1e9 + 7;
  22. const ll INF = 1e8;
  23. const int maxn = 1e5 + 5;
  24. typedef pair<double, double> pi;
  25. typedef pair<int, pair<int,int>> pii;
  26. typedef pair<ll, ll> pl;
  27. typedef pair<ll, pair<ll,ll>>pll;
  28.  
  29. struct edge{
  30.     int u,v,w;
  31.     edge(int u = 0, int v = 0, int w = 0)
  32.     {
  33.         this->u = u;
  34.         this->v = v;
  35.         this->w = w;
  36.     }
  37. };
  38. struct matrix{
  39.     ll val[3][3];
  40.     matrix(){
  41.         memset(val, 0, sizeof(val));
  42.     }
  43. };
  44.  
  45. const int N = 1e4 + 10;
  46.  
  47. ll n, c, h[N], ans = +INF;
  48.  
  49. void nhap(){
  50. 	cin >> n >> c;
  51. 	FOR(i, 1, n) cin >> h[i];
  52. }
  53. namespace sub2{
  54. 	const int limit = 110;
  55. 	bool check(){
  56. 		FOR(i, 1, n) if(h[i] > 100) return 0;
  57. 		return n <= 1000;
  58. 	}
  59. 	ll dp[1010][120];
  60. 	void solve(){
  61. 		FOR(i, 1, n) FOR(j, 0, limit) dp[i][j] = +INF;
  62. 		FOR(i, h[1], limit)
  63. 			dp[1][i] = 1LL * (i - h[1]) * 1LL * (i - h[1]);
  64. 		FOR(i, 2, n) FOR(j, h[i], limit){
  65. 			FOR(k, h[i - 1], limit){
  66. 				if(dp[i - 1][k] == +INF) continue;
  67. 				minimize(dp[i][j], dp[i - 1][k] + 1LL * abs(j - k) * c + 1LL * (j - h[i]) * 1LL * (j - h[i]));
  68. 			}
  69. 		}
  70. 		FOR(i, h[n], limit) minimize(ans, dp[n][i]);
  71. 		cout << ans;
  72. 	}
  73. }
  74. namespace sub3{
  75. 	const int limit = 1e3 + 10;
  76. 	ll dp[10010][limit + 20], min1V[10010][limit + 20], min2V[10010][limit + 20], ans = +INF;
  77.  
  78. 	void solve(){
  79. 		FOR(i, 1, n) FOR(j, 0, limit + 1){
  80. 			dp[i][j] = +INF;
  81. 			min1V[i][j] = +INF;
  82. 			min2V[i][j] = +INF;
  83. 		}
  84. 		FOR(i, h[1], limit) 
  85. 			dp[1][i] = 1LL * (i - h[1]) * 1LL * (i - h[1]);
  86. 		FOR(i, 2, n){
  87. 			FOR(j, 1, limit) min1V[i - 1][j] = min(min1V[i - 1][j - 1], dp[i - 1][j] - c * j);
  88. 			FORD(j, limit, 1) min2V[i - 1][j] = min(min2V[i - 1][j + 1], dp[i - 1][j] + c * j);
  89. 			FOR(j, h[i], limit){
  90. 				dp[i][j] = min(1LL * min1V[i - 1][j] + 1LL * c * j, 1LL * min2V[i - 1][j + 1] - 1LL * c * j) + 1LL * (j - h[i]) * 1LL * (j - h[i]);
  91. 			}
  92. 		}
  93. 		FOR(i, h[n], limit) minimize(ans, dp[n][i]);
  94. 		cout << ans;
  95. 	}
  96. }
  97. int main(){
  98.     ios_base::sync_with_stdio(0);
  99.     cin.tie(0); cout.tie(0);
  100.     nhap();
  101.     sub3::solve();
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0.01s 7716KB
comments (?)
stdin
copy 
5 2 
2 
3 
5 
1 
4
stdout
copy 
15
https://ideone.com/LCOzAM
language:
C++14 (gcc 8.3)
created:
9 days 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!