fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ldb long double
  4. #define fi first
  5. #define se second
  6. #define sza(a) (int)a.size()
  7. #define pir pair<int,int>
  8. #define pirll pair<ll,ll>
  9. using namespace std;
  10. const int maxn = 4e3 + 5;
  11. const int modu = 1e9 + 7;
  12.  
  13. inline void add(ll &x,ll y){x = (x + y) % modu;}
  14.  
  15. ll dp[maxn][maxn],a[maxn],f[maxn][maxn],predq[maxn][maxn];
  16.  
  17. void absorb_f(int p,int nxt,int m){
  18. 	for (int i = 0 ; i <= m ; i++){
  19. 	  add(f[p][i],f[nxt][i]);
  20.  
  21.       if (a[nxt] < a[p])
  22.         add(f[p][i],dp[nxt][i]);
  23. 	}
  24. }
  25.  
  26. void get_dp(int p,int lst,int m){
  27. 	for (int i = a[p] ; i <= m ; i++)
  28. 	  add(dp[p][i],predq[lst][i - a[p]]);
  29. }
  30.  
  31. void get_predq(int p,int lst,int m){
  32. 	for (int i = 0 ; i <= m ; i++)
  33. 	  predq[p][i] = ((ll)predq[lst][i] + (ll)f[p][i]) % modu;
  34. }
  35.  
  36. void perform_dynamic_programming(int n,int m){
  37. 	deque <int> dq,tdq;
  38.  
  39. 	for (int i = 1 ; i <= n ; i++){
  40. 		//a[i] cannot be chosen, as a[i] > -> seen together
  41. 		while (dq.size() && a[i] > a[dq.back()]){
  42. 			absorb_f(i,dq.back(),m);
  43. 			dq.pop_back();
  44. 		}
  45. 		while (tdq.size() && a[i] >= a[tdq.back()]) tdq.pop_back();
  46.  
  47. 		//self case
  48. 		dp[i][a[i]]++;
  49.  
  50. 		if (tdq.size())
  51. 		  get_dp(i,tdq.back(),m);
  52.  
  53. 		if (dq.size())
  54. 			get_predq(i,dq.back(),m);
  55. 		else 
  56. 		    get_predq(i,0,m);
  57.  
  58.  
  59. 		dq.push_back(i);
  60. 		tdq.push_back(i);
  61. 	}
  62. }
  63.  
  64. int solve(int n,int m){
  65. 	ll res = 0;
  66.  
  67. 	perform_dynamic_programming(n,m);
  68.  
  69. 	for (int i = 1 ; i <= n ; i++){
  70. 		for (int j = 0 ; j <= m ; j++)
  71. 		  res = (res + dp[i][j]) % modu;
  72. 	}
  73. 	res++;
  74. 	if (res < 0) res += modu;
  75. 	return res;
  76. }
  77.  
  78. int main(){
  79. 	ios_base::sync_with_stdio(false);
  80. 	cin.tie(0);cout.tie(0);
  81.  
  82. 	int n,m;
  83. 	cin >> n >> m;
  84. 	for (int i = 1 ; i <= n ; i++) cin >> a[i];
  85.  
  86. 	cout << solve(n,m);
  87.  
  88. 	return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/hk65fM
language:
C++14 (gcc 8.3)
created:
1 day 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!