QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#420624	#2836. Permutation Pattern	alpha1022	AC ✓	184ms	101744kb	C++14	901b	2024-05-24 20:44:13	2024-05-24 20:44:14

Judging History

你现在查看的是最新测评结果

[2024-05-24 20:44:14]
评测

测评结果：AC
用时：184ms
内存：101744kb

查看

[2024-05-24 20:44:13]
提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 50;

int n, p[N + 5], q[N + 5];
ll f[N + 5][N + 5][N + 5][N + 5], g[N + 5][N + 5][N + 5][N + 5];

bool solve() {
  if (scanf("%d", &n) == -1) return 0;
  for (int i = 1; i <= n; ++i) scanf("%d", p + i), q[p[i]] = i;
  for (int l = n; l; --l)
    for (int r = l; r <= n; ++r)
      for (int u = n; u; --u)
        for (int v = u; v <= n; ++v) {
          int k = q[v];
          if (k >= l && k <= r) {
            f[l][r][u][v] = g[l][k - 1][u][v - 1] + g[k + 1][r][u][v - 1] + 1;
            for (int i = u; i < v; ++i) f[l][r][u][v] += f[l][k - 1][u][i] * g[k + 1][r][i + 1][v - 1];
          } else f[l][r][u][v] = 0;
          g[l][r][u][v] = g[l][r][u][v - 1] + f[l][r][u][v];
        }
  printf("%lld\n", g[1][n][1][n]);
  return 1;
}

int T;

int main() {
  while (solve());
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 10164kb

input:

output:

3
7
11

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 10056kb

input:

output:

result:

ok 9 lines

Test #3:

score: 0

Accepted

time: 2ms

memory: 12164kb

input:

output:

result:

ok 100 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 9968kb

input:

output:

result:

ok 24 lines

Test #5:

score: 0

Accepted

time: 0ms

memory: 12248kb

input:

output:

result:

ok 100 lines

Test #6:

score: 0

Accepted

time: 0ms

memory: 10144kb

input:

output:

result:

ok 20 lines

Test #7:

score: 0

Accepted

time: 0ms

memory: 12292kb

input:

6
3 4 5 1 6 2
6
3 4 5 6 1 2
6
4 2 5 6 3 1
6
3 5 2 6 4 1
6
3 2 4 1 5 6
6
5 1 4 3 2 6
6
4 6 3 2 1 5
6
3 4 6 5 1 2
6
5 1 2 6 4 3
6
3 5 2 6 1 4
6
6 5 4 1 2 3
6
1 3 2 5 4 6
6
2 3 1 5 4 6
6
1 4 6 3 5 2
6
3 2 4 5 6 1
6
1 2 6 3 4 5
6
5 4 6 1 2 3
6
4 1 2 5 3 6
6
4 1 3 5 2 6
6
6 1 5 2 4 3
6
2 3 1 5 6 4
6
1 4 ...

output:

result:

ok 83 lines

Test #8:

score: 0

Accepted

time: 2ms

memory: 14200kb

input:

7
2 1 4 3 5 7 6
7
5 4 7 6 3 2 1
7
7 2 5 3 6 4 1
7
6 3 1 5 4 2 7
7
6 5 4 7 2 1 3
7
4 1 7 2 5 3 6
7
5 3 1 6 2 7 4
7
3 7 1 6 5 4 2
7
6 2 1 5 4 3 7
7
4 7 6 3 1 2 5
7
4 6 3 7 1 2 5
7
6 5 2 1 7 3 4
7
4 1 2 6 3 7 5
7
3 1 6 7 5 2 4
7
4 7 3 6 1 5 2
7
3 6 5 4 7 1 2
7
1 7 2 4 3 5 6
7
2 6 1 3 5 7 4
7
1 2 7 4 6 ...

output:

result:

ok 71 lines

Test #9:

score: 0

Accepted

time: 2ms

memory: 14444kb

input:

8
4 1 2 7 8 5 6 3
8
7 2 8 6 4 5 1 3
8
2 3 4 8 6 5 1 7
8
5 8 3 6 2 1 4 7
8
2 4 3 8 1 7 5 6
8
5 7 8 4 6 3 1 2
8
1 4 2 7 5 3 8 6
8
6 7 8 4 3 1 2 5
8
7 2 5 1 6 4 8 3
8
8 1 4 7 2 5 6 3
8
6 8 7 3 2 1 5 4
8
7 6 8 2 1 3 5 4
8
1 5 6 4 2 7 3 8
8
6 3 2 7 8 4 1 5
8
6 2 3 7 4 5 8 1
8
4 5 7 1 8 3 2 6
8
7 4 1 6 5 ...

output:

result:

ok 62 lines

Test #10:

score: 0

Accepted

time: 0ms

memory: 16420kb

input:

9
2 3 7 8 9 6 1 5 4
9
1 6 3 4 2 9 8 7 5
9
1 9 2 6 7 3 4 5 8
9
4 2 1 5 6 3 9 7 8
9
5 1 2 4 3 8 6 9 7
9
5 3 6 2 9 8 7 1 4
9
2 1 9 8 5 3 6 4 7
9
5 4 1 7 8 3 9 6 2
9
2 1 9 6 5 4 8 3 7
9
5 3 6 4 9 2 7 1 8
9
3 7 1 4 6 9 8 5 2
9
5 1 9 4 8 7 3 2 6
9
5 8 7 4 9 6 3 2 1
9
5 7 2 1 3 9 4 6 8
9
9 8 5 1 4 6 7 3 2
...

output:

result:

ok 55 lines

Test #11:

score: 0

Accepted

time: 3ms

memory: 18520kb

input:

10
3 8 6 9 7 5 2 1 4 10
10
9 4 6 10 2 5 3 1 8 7
10
7 8 5 10 2 9 3 1 4 6
10
8 6 9 10 7 3 4 5 2 1
10
5 2 4 3 8 6 1 7 9 10
10
1 2 8 4 5 7 10 9 6 3
10
8 3 4 6 5 10 9 7 2 1
10
3 9 10 4 5 1 2 8 6 7
10
4 8 2 3 9 10 5 6 1 7
10
2 3 4 1 8 7 9 5 10 6
10
4 10 6 2 3 1 8 5 7 9
10
8 7 6 2 4 9 10 1 5 3
10
1 9 6 5 1...

output:

result:

ok 50 lines

Test #12:

score: 0

Accepted

time: 3ms

memory: 18636kb

input:

2
2 1
8
3 8 1 6 2 7 4 5
2
2 1
3
2 1 3
6
3 4 6 5 1 2
1
1
4
2 4 3 1
1
1
6
1 3 4 2 6 5
9
5 8 9 2 1 3 7 4 6
2
1 2
9
4 3 7 9 1 2 5 6 8
6
4 6 1 5 3 2
4
3 1 4 2
6
2 1 3 6 4 5
2
1 2
2
1 2
7
4 7 2 3 5 1 6
2
2 1
1
1
7
2 7 6 5 1 4 3
2
2 1
4
3 1 2 4
8
7 8 2 6 5 1 4 3
9
4 5 1 2 6 3 7 9 8
10
1 3 2 9 5 7 8 10 6 4
...

output:

result:

ok 50 lines

Test #13:

score: 0

Accepted

time: 161ms

memory: 99628kb

input:

50
3 50 12 35 11 7 17 49 1 9 41 5 4 27 6 22 8 20 44 43 10 13 15 42 38 16 18 19 30 2 23 21 34 24 32 25 45 39 40 48 26 28 37 36 33 31 29 47 46 14
50
41 21 40 37 36 31 30 3 2 1 34 27 8 4 5 9 28 17 10 11 7 12 15 38 13 14 6 18 20 25 24 16 22 29 26 35 32 33 46 45 50 42 47 48 49 23 43 39 44 19
50
41 38 23 ...

output:

71786596197
925094043175
15360313400319
83273752556543
599976015791
6320724096624
5783738400607
487480246255
307563605
419463685996543

result:

ok 10 lines

Test #14:

score: 0

Accepted

time: 163ms

memory: 99140kb

input:

50
34 20 49 44 4 16 7 24 26 46 31 12 22 47 17 21 29 14 23 9 11 2 30 33 18 8 19 13 38 15 39 28 48 27 35 3 40 42 37 6 25 32 43 10 45 1 50 41 5 36
50
2 29 24 7 1 3 8 4 12 5 6 10 9 26 11 23 13 44 14 16 41 37 15 19 20 34 33 32 21 45 40 22 17 28 25 27 18 30 31 35 38 36 39 43 42 50 46 49 47 48
50
28 19 18 ...

output:

469303887
3708187017215
320672525975551
2384027442511
7802888619
54571757666
12111593784831
124903382056959
22915448657023
181636580245503

result:

ok 10 lines

Test #15:

score: 0

Accepted

time: 157ms

memory: 96112kb

input:

50
1 2 3 16 5 4 6 12 10 9 8 7 11 14 13 15 42 41 40 21 17 19 18 20 26 25 22 24 23 28 27 39 29 36 32 31 30 33 35 34 38 37 43 45 44 50 46 47 48 49
50
24 30 13 12 44 9 8 6 26 1 5 3 10 11 23 15 14 16 18 17 21 19 22 37 25 33 27 2 32 31 28 29 40 36 20 34 50 47 41 4 38 42 43 46 45 48 39 35 7 49
50
45 44 25 ...

output:

1125899906842623
1973544596971
20464777601
145970369134591
1125899906842623
27103062537
492677980225535
611302507087
9436138365023
16901739359823

result:

ok 10 lines

Test #16:

score: 0

Accepted

time: 154ms

memory: 100016kb

input:

50
16 15 13 12 11 4 3 2 1 5 10 30 27 8 6 7 9 22 38 20 19 14 17 37 31 29 23 21 26 24 25 33 32 36 34 39 41 28 40 45 44 43 35 18 42 46 48 47 49 50
50
49 48 43 42 41 24 23 22 29 5 39 3 2 1 4 21 19 8 33 7 9 10 17 12 11 14 13 15 6 16 18 20 40 26 25 37 31 30 28 27 35 34 32 36 38 47 44 46 45 50
50
26 25 24 ...

output:

16941091848191
76454653671423
1125899906842623
281482263953919
1853535582743
11131049930979
914793674309631
109343881936895
323479068999679
226499395534975

result:

ok 10 lines

Test #17:

score: 0

Accepted

time: 161ms

memory: 101680kb

input:

50
48 47 46 45 44 30 35 24 3 16 12 10 4 2 1 9 8 7 6 15 13 14 31 28 27 18 19 20 17 11 25 21 26 5 23 43 29 34 32 33 37 38 36 39 40 22 42 41 49 50
50
50 13 47 44 43 49 42 34 32 31 30 28 27 26 25 14 9 8 7 5 24 3 1 4 12 6 10 2 16 15 11 21 20 18 17 19 22 23 29 33 35 37 36 39 38 40 41 46 45 48
50
46 43 25 ...

output:

13401186994175
58470124486783
3963515139491
18417882639247
1483926119947
74820097933311
76869894769151
138492980779
86510044435583
986103193471

result:

ok 10 lines

Test #18:

score: 0

Accepted

time: 147ms

memory: 99760kb

input:

50
50 49 48 47 45 42 41 40 39 38 18 17 16 1 15 14 5 4 2 3 7 6 8 13 11 10 9 12 32 27 26 25 24 19 20 23 21 22 28 29 31 30 37 33 36 35 34 43 44 46
50
3 1 2 5 4 11 6 33 43 19 8 21 18 17 9 13 10 34 12 15 16 20 31 29 22 24 25 26 28 7 30 42 41 32 35 38 27 37 36 40 39 44 45 23 46 49 48 47 14 50
50
46 45 44 ...

output:

1125899906842623
11503392639871
268613428707327
15555678637567
9233630159167
22814306219679
170131707658239
633318697600255
774159265169407
143738636705815

result:

ok 10 lines

Test #19:

score: 0

Accepted

time: 160ms

memory: 99620kb

input:

50
33 30 29 39 28 50 27 24 23 22 21 20 19 18 15 4 7 2 3 25 5 8 1 6 14 11 9 10 32 12 13 16 17 26 31 37 34 35 36 40 38 41 42 43 45 44 46 49 47 48
50
37 36 32 25 22 21 20 19 12 9 7 3 2 1 4 5 6 8 10 11 18 17 15 13 14 16 24 23 26 27 29 28 30 31 35 34 33 38 39 40 41 46 42 44 43 45 50 47 48 49
50
8 7 6 5 1...

output:

38933422040063
1125899906842623
562950014763007
44651459044351
26429508299007
22574688062335
50191439772447
48552580405247
976228746199
286807572873215

result:

ok 10 lines

Test #20:

score: 0

Accepted

time: 150ms

memory: 101664kb

input:

50
2 12 3 6 5 4 11 8 10 39 9 15 13 14 25 34 31 38 32 29 19 17 16 18 28 7 27 20 22 21 23 26 24 30 40 37 35 41 33 1 49 43 42 36 48 47 44 45 46 50
50
49 45 43 39 24 38 28 27 25 23 22 20 19 18 3 2 1 17 6 13 4 15 14 29 11 7 8 12 21 37 36 35 26 9 34 32 44 31 30 33 10 42 41 16 40 48 46 47 50 5
50
6 5 4 3 2...

output:

17351472343295
4556477881839
2463120461823
10732306780233
1125899906842623
1125899906842623
914793674309631
360661339078655
56122596884479
1125899906842623

result:

ok 10 lines

Test #21:

score: 0

Accepted

time: 151ms

memory: 101744kb

input:

50
13 11 10 7 12 6 5 2 1 3 4 9 8 14 15 16 18 17 20 19 26 22 21 25 24 23 27 28 29 30 32 31 35 34 33 36 40 39 37 38 41 42 44 43 46 45 47 48 49 50
50
33 5 4 3 2 1 31 27 10 9 6 8 7 25 24 12 15 13 14 23 22 20 19 16 18 17 21 26 29 28 30 32 34 43 37 39 35 36 38 42 40 11 41 44 46 45 47 48 50 49
50
12 9 4 2 ...

output:

636067476668415
457397606285311
562949953748991
193106020401151
156758753177599
562950161039359
1125899906842623
174067508416955
12327032671235
130364051111935

result:

ok 10 lines

Test #22:

score: 0

Accepted

time: 146ms

memory: 99696kb

input:

50
23 22 21 20 30 19 18 17 6 24 5 1 2 3 4 7 8 15 9 27 10 14 12 11 13 16 28 26 34 41 32 31 29 35 33 40 39 36 37 38 42 49 47 25 43 44 46 45 48 50
50
44 40 39 29 45 20 6 16 1 2 4 3 5 18 11 7 8 10 9 15 13 12 14 17 19 25 21 22 23 35 24 26 28 27 30 37 36 34 32 31 33 38 41 42 46 43 49 48 47 50
50
22 21 18 ...

output:

52374859921919
183793727635071
1125899906842623
164982120296479
291112892864703
84576527974399
149606796066815
1125899906842623
1125899906842623
26141702275847

result:

ok 10 lines

Test #23:

score: 0

Accepted

time: 184ms

memory: 101672kb

input:

50
19 27 40 18 49 41 4 42 23 44 13 12 6 14 20 17 28 35 43 21 15 29 34 2 38 48 10 9 32 31 22 11 3 50 36 45 8 25 30 37 1 5 24 16 26 7 33 39 46 47
50
12 26 47 33 38 49 1 20 39 17 42 18 37 6 30 19 22 23 5 31 45 41 9 16 34 10 7 35 46 50 2 24 11 40 4 32 27 13 48 14 36 3 43 44 8 25 28 21 29 15
50
22 32 36 ...

output:

result:

ok 10 lines

Test #24:

score: 0

Accepted

time: 11ms

memory: 98864kb

input:

50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

output:

1125899906842623

result:

ok single line: '1125899906842623'