QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#83363	#2836. Permutation Pattern	uniecho1^#	AC ✓	1035ms	35168kb	C++14	1.6kb	2023-03-01 16:52:13	2023-03-01 16:52:16

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-01 16:52:16]
评测

测评结果：AC
用时：1035ms
内存：35168kb

查看

[2023-03-01 16:52:13]
提交

answer

#include <bits/stdc++.h>
using namespace std;
int n;
int a[55];
long long f[55][55][55][55];
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for (int l1 = 0; l1 < n; ++l1) {
            for (int l = 1; l <= n - l1; ++l) {
                int r = l + l1;
                for (int l2 = 0; l2 < n; ++l2) {
                    for (int minn = 1; minn <= n - l2; ++minn) {
                        int maxx = minn + l2;
                        f[l][r][minn][maxx] = 0;
                        int p = 0;
                        int x = 0;
                        for (int i = l; i <= r; ++i)
                            if (a[i] >= minn && a[i] <= maxx && p < a[i]) {
                                p = a[i];
                                x = i;
                            }
                        if (x) {
                            for (int i = minn; i <= maxx; ++i) {
                                f[l][r][minn][maxx] +=
                                    (f[l][x - 1][minn][i] -
                                     f[l][x - 1][minn][i - 1]) *
                                    f[x + 1][r][i + 1][maxx];
                            }
                            f[l][r][minn][maxx] += f[x + 1][r][minn][p - 1];
                            f[l][r][minn][maxx] += f[l][x - 1][minn][p - 1] + 1;
                            f[l][r][minn][maxx] += f[l][r][minn][p - 1];
                        }
                    }
                }
            }
        }
        printf("%lld\n", f[1][n][1][n]);
    }
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 5552kb

input:

output:

3
7
11

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 5552kb

input:

output:

result:

ok 9 lines

Test #3:

score: 0

Accepted

time: 0ms

memory: 5512kb

input:

output:

result:

ok 100 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 5740kb

input:

output:

result:

ok 24 lines

Test #5:

score: 0

Accepted

time: 0ms

memory: 5564kb

input:

output:

result:

ok 100 lines

Test #6:

score: 0

Accepted

time: 2ms

memory: 5736kb

input:

output:

result:

ok 20 lines

Test #7:

score: 0

Accepted

time: 2ms

memory: 3596kb

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: 3ms

memory: 3592kb

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: 4ms

memory: 3748kb

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: 5700kb

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: 5836kb

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: 1ms

memory: 3928kb

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: 976ms

memory: 34892kb

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: 995ms

memory: 33916kb

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: 979ms

memory: 35168kb

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: 955ms

memory: 33976kb

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: 957ms

memory: 34896kb

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: 997ms

memory: 33756kb

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: 999ms

memory: 35116kb

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: 958ms

memory: 33756kb

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: 992ms

memory: 34268kb

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: 941ms

memory: 34696kb

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: 1035ms

memory: 34452kb

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: 74ms

memory: 34664kb

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'