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 mul(int x , int y){
  27.     return (1ll * x * y) % mod;
  28. }
  29.  
  30. int n , m , a[maxN] , dp[maxN][maxN];
  31. bool mark[maxN][maxN];
  32.  
  33. namespace sub1{
  34.     bool check(){
  35.         return (n <= 100 && m <= 400);
  36.     }
  37.  
  38.     void solve(){
  39.         for (int i = 1 ; i <= n ; i++){
  40.             int cur = INT_MIN;
  41.             for (int j = i ; j <= n ; j++){
  42.                 cur = max(cur , a[j]);
  43.                 if (i > 1 && j < n){
  44.                     mark[i - 1][j + 1] = (cur > max(a[i - 1] , a[j + 1]));
  45.                 }
  46.             }
  47.         }
  48.         for (int i = 1 ; i <= n ; i++){
  49.             dp[i][a[i]] = 1;
  50.             for (int t = a[i] ; t <= m ; t++){
  51.                 for (int j = 1 ; j < i ; j++){
  52.                     if (mark[j][i] == 1) self_add(dp[i][t] , dp[j][t - a[i]]);
  53.                 }
  54.             }
  55.         }
  56.         int ans = 1;
  57.         for (int i = 1 ; i <= n ; i++){
  58.             for (int t = 1 ; t <= m ; t++){
  59.                 self_add(ans , dp[i][t]);
  60.             }
  61.         }
  62.         cout << ans << "\n";
  63.     }
  64. }
  65.  
  66. void solve(){
  67.     cin >> n >> m;
  68.     for (int i = 1 ; i <= n ; i++) cin >> a[i];
  69.     if (sub1::check()) return sub1::solve();
  70. }
  71.  
  72. #define name "K"
  73.  
  74. int main(){
  75.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  76.     if (fopen(name".INP" , "r")){
  77.         freopen(name".INP" , "r" , stdin);
  78.         freopen(name".OUT" , "w" , stdout);
  79.     }
  80.     int t = 1; //cin >> t;
  81.     while (t--) solve();
  82.     return 0;
  83. }
  84.  
  85.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/Do3nBq
language:
C++ (gcc 8.3)
created:
3 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!