fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = 4007;
  14. const int mod = int(1e9)+7;
  15.  
  16. int add(int x , int y){
  17.     x += y;
  18.     if (x >= mod) x -= mod;
  19.     return x;
  20. }
  21.  
  22. void self_add(int &x , int y){
  23.     x = add(x , y);
  24. }
  25.  
  26. int sub(int x , int y){
  27.     x -= y;
  28.     if (x < 0) x += mod;
  29.     return x;
  30. }
  31.  
  32. void self_sub(int &x , int y){
  33.     x = sub(x , y);
  34. }
  35.  
  36. int mul(int x , int y){
  37.     return (1ll * x * y) % mod;
  38. }
  39.  
  40. int n , m , a[maxN] , dp[maxN][maxN];
  41. bool mark[maxN][maxN];
  42.  
  43. namespace sub1{
  44.     bool check(){
  45.         return (n <= 100 && m <= 400);
  46.     }
  47.  
  48.     void solve(){
  49.         for (int i = 1 ; i <= n ; i++){
  50.             int cur = INT_MIN;
  51.             for (int j = i ; j <= n ; j++){
  52.                 cur = max(cur , a[j]);
  53.                 if (i > 1 && j < n){
  54.                     mark[i - 1][j + 1] = (cur > max(a[i - 1] , a[j + 1]));
  55.                 }
  56.             }
  57.         }
  58.         for (int i = 1 ; i <= n ; i++){
  59.             dp[i][a[i]] = 1;
  60.             for (int t = a[i] ; t <= m ; t++){
  61.                 for (int j = 1 ; j < i ; j++){
  62.                     if (mark[j][i] == 1) self_add(dp[i][t] , dp[j][t - a[i]]);
  63.                 }
  64.             }
  65.         }
  66.         int ans = 1;
  67.         for (int i = 1 ; i <= n ; i++){
  68.             for (int t = 1 ; t <= m ; t++){
  69.                 self_add(ans , dp[i][t]);
  70.             }
  71.         }
  72.         cout << ans << "\n";
  73.     }
  74. }
  75.  
  76. namespace sub2{
  77.     int pre[maxN][maxN] , sum_pre[maxN];
  78.     bool del[maxN];
  79.  
  80.     void solve(){
  81.         deque<int> dq;
  82.         for (int i = 1 ; i <= n ; i++){
  83.             while (dq.empty() == 0 && a[dq.back()] <= a[i]){
  84.                 int j = dq.back();
  85.                 for (int t = 1 ; t <= m ; t++){
  86.                     self_sub(sum_pre[t] , pre[j][t]);
  87.                     self_add(pre[i][t] , pre[j][t]);
  88.                 }
  89.                 if (a[j] < a[i]){
  90.                     for (int t = 1 ; t <= m ; t++){
  91.                         self_add(pre[i][t] , dp[j][t]);
  92.                     }
  93.                 }
  94.                 else{
  95.                     del[j] = 1;
  96.                     for (int t = 1 ; t <= m ; t++){
  97.                         self_add(dp[i][t] , dp[j][t]);
  98.                     }
  99.                 }
  100.                 dq.pop_back();
  101.             }
  102.             self_add(dp[i][a[i]] , 1);
  103.             for (int t = a[i] ; t <= m ; t++){
  104.                 self_add(dp[i][t] , sum_pre[t - a[i]]);
  105.             }
  106.             dq.push_back(i);
  107.             for (int t = 1 ; t <= m ; t++) self_add(sum_pre[t] , pre[i][t]);
  108.         }
  109.         int ans = 1;
  110.         for (int i = 1 ; i <= n ; i++){
  111.             for (int t = 1 ; t <= m ; t++){
  112.                 if (del[i] == 0) self_add(ans , dp[i][t]);
  113.             }
  114.         }
  115.         cout << ans << "\n";
  116.     }
  117. }
  118.  
  119. void solve(){
  120.     cin >> n >> m;
  121.     for (int i = 1 ; i <= n ; i++) cin >> a[i];
  122.     //if (sub1::check()) return sub1::solve();
  123.     return sub2::solve();
  124. }
  125.  
  126. #define name "K"
  127.  
  128. int main(){
  129.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  130.     if (fopen(name".INP" , "r")){
  131.         freopen(name".INP" , "r" , stdin);
  132.         freopen(name".OUT" , "w" , stdout);
  133.     }
  134.     int t = 1; //cin >> t;
  135.     while (t--) solve();
  136.     return 0;
  137. }
  138.  
  139.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/KK2u03
language:
C++ (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!