fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 2001, MOD = 1e9 + 7;
  4.  
  5. int n, b, f[N], dp[N][N];
  6.  
  7. int main() {
  8.   ios::sync_with_stdio(false);
  9.   cin.tie(0);
  10.  
  11.   if (fopen("GRAPH.INP", "r")) {
  12.     freopen("GRAPH.INP", "r", stdin);
  13.     freopen("GRAPH.OUT", "w", stdout);
  14.   }
  15.  
  16.   cin >> n >> b;
  17.   for (int i = 1; i <= n; ++i) {
  18.     cin >> f[i];
  19.   }
  20.  
  21.   for (int gz = 0; gz <= n; ++gz) {
  22.     dp[0][gz] = 1;
  23.   }
  24.   for (int i = 1; i <= n; ++i) {
  25.     for (int gz = 0; gz <= n - i; ++gz) {
  26.       if (f[i] != -1) {
  27.         // forced
  28.         if (f[i] < i && f[i] + gz <= b) {
  29.           dp[i][gz] = dp[i - 1][gz + (f[i] > 0)];
  30.         }
  31.       } else {
  32.         // choice
  33.         for (int j = 0; j < i; ++j) {
  34.           if (j + gz <= b) {
  35.             dp[i][gz] += dp[i - 1][gz + (j > 0)];
  36.             if (dp[i][gz] >= MOD) {
  37.               dp[i][gz] -= MOD;
  38.             }
  39.           }
  40.         }
  41.       }
  42.     }
  43.   }
  44.  
  45.   cout << dp[n][0] << '\n';
  46.   return 0;
  47. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
4 2
0 1 1 1
stdout 
0
https://ideone.com/mOVTXm
VOI22 - GRAPH - Subtask 3
language:
C++14 (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!