oj.uz

Submission #109693

# Submission time Handle Problem Language Result Execution time Memory
109693 2019-05-07T13:57:28 Z IOrtroiii Tents (JOI18_tents) C++14
100 / 100
 159 ms 35832 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3030;
const int mod = 1e9 + 7;

void add(int &x,int y) {
   x += y; if (x >= mod) x -= mod;
}

int mul(int x,int y) {
   return (long long) x * y % mod;
}

int f[N][N];

int main() {
   int n, m; scanf("%d %d", &n, &m);
   f[m][n] = 1;
   for (int i = m; i >= 0; --i) {
      for (int j = n; j >= 0; --j) {
         if (i) {
            add(f[i - 1][j], f[i][j]);
            if (j) add(f[i - 1][j - 1], mul(mul(4, j), f[i][j]));
            if (j > 1) add(f[i - 1][j - 2], mul(mul(j, j - 1), mul(mod + 1 >> 1, f[i][j])));
            if (i > 1 && j) add(f[i - 2][j - 1], mul(mul(j, i - 1), f[i][j]));
         } else if (j) add(f[i][j - 1], f[i][j]);
      }
   }
   printf("%d\n", (f[0][0] + mod - 1) % mod);
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:26:72: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             if (j > 1) add(f[i - 1][j - 2], mul(mul(j, j - 1), mul(mod + 1 >> 1, f[i][j])));
                                                                    ~~~~^~~
tents.cpp:19:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int n, m; scanf("%d %d", &n, &m);
              ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 1408 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 4 ms 1024 KB Output is correct
11 Correct 4 ms 1536 KB Output is correct
12 Correct 5 ms 1920 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 1408 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 4 ms 1024 KB Output is correct
11 Correct 4 ms 1536 KB Output is correct
12 Correct 5 ms 1920 KB Output is correct
13 Correct 14 ms 7680 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 109 ms 24312 KB Output is correct
16 Correct 16 ms 7928 KB Output is correct
17 Correct 37 ms 12536 KB Output is correct
18 Correct 42 ms 11740 KB Output is correct
19 Correct 117 ms 26916 KB Output is correct
20 Correct 110 ms 25564 KB Output is correct
21 Correct 81 ms 21980 KB Output is correct
22 Correct 63 ms 18936 KB Output is correct
23 Correct 34 ms 7672 KB Output is correct
24 Correct 155 ms 35832 KB Output is correct
25 Correct 119 ms 30968 KB Output is correct
26 Correct 135 ms 32544 KB Output is correct
27 Correct 159 ms 35556 KB Output is correct