QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#244782	#2836. Permutation Pattern	Delay_for_five_minutes^#	AC ✓	536ms	140932kb	C++20	2.7kb	2023-11-09 15:49:43	2023-11-09 15:50:14

Judging History

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

[2023-11-09 15:50:14]
评测

测评结果：AC
用时：536ms
内存：140932kb

查看

[2023-11-09 15:49:43]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
int p[55];
typedef long long ll;
ll f[55][55][55][55];
ll g[55][55][55][55];
void upd(ll &x,ll y) {
    x += y;
}
int main()
{
   // freopen("in.txt","r",stdin) ;
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    while(cin >> n) {
        for(int i = 1;i <= n;i++) cin >> p[i];
        for(int i = 0;i <= n;i++) for(int j = i;j <= n;j++) for(int k = 0;k <= n;k++) for(int l = k;l <= n;l++) f[i][j][k][l] = 0;
        ll x , y;
        for(int l = n;l >= 1;l--) {
            for(int r = l;r <= n;r++) {
                for(int vl = 1;vl <= n;vl++) {
                    for(int vr = vl;vr <= n;vr++) {
                        if(l == r) {
                            if(vl == vr && vl == p[l]) f[l][r][vl][vr] = 1;
                            else f[l][r][vl][vr] = 0;
                        }
                        else {
                            ll &ans = f[l][r][vl][vr] ;
                            for(int k = l;k <= r;k++) {
                                if(p[k] == vr) {
                                    ///k as max

                                    /// both empty
                                    if(vl == vr && vl == p[k]) {ans++ ; continue ;}
                                    
                                    for(int vk = vl ; vk < p[k];vk++) {
                                        ///
                                        ans += f[l][k - 1][vl][vk] * g[k + 1][r][vk + 1][p[k]] ;
                                    }
                                    ///left empty
                                    for(int up = vl ; up < p[k];up++)
                                        ans += f[k + 1][r][vl][up] ;
                                    ///right empty
                                    for(int up = vl ; up < p[k];up++)
                                        ans += f[l][k - 1][vl][up] ;
                                }
                            }
                        }
                        // cout << l <<' ' << r <<' ' << vl <<' ' << vr <<' ' << f[l][r][vl][vr] << '\n' ;
                    }
                }
                for(int vl = n;vl >= 1;vl--) {
                    for(int vr = vl;vr <= n;vr++) {
                        if(vl == vr) g[l][r][vl][vr] = f[l][r][vl][vr];
                        else {
                            g[l][r][vl][vr] = g[l][r][vl][vr-1] + g[l][r][vl+1][vr] - g[l][r][vl+1][vr-1] + f[l][r][vl][vr];
                        }
                    }
                }
            }
        }

        ll ans = 0;
        ans = g[1][n][1][n] ;
        cout << ans << '\n' ;

    }
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 13908kb

input:

output:

3
7
11

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 13864kb

input:

output:

result:

ok 9 lines

Test #3:

score: 0

Accepted

time: 3ms

memory: 18004kb

input:

output:

result:

ok 100 lines

Test #4:

score: 0

Accepted

time: 0ms

memory: 13976kb

input:

output:

result:

ok 24 lines

Test #5:

score: 0

Accepted

time: 2ms

memory: 17908kb

input:

output:

result:

ok 100 lines

Test #6:

score: 0

Accepted

time: 2ms

memory: 17984kb

input:

output:

result:

ok 20 lines

Test #7:

score: 0

Accepted

time: 0ms

memory: 22016kb

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

memory: 24076kb

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

memory: 26152kb

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

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

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

memory: 26184kb

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

memory: 140868kb

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

memory: 136740kb

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

memory: 136744kb

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

memory: 137076kb

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

memory: 136772kb

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

memory: 140868kb

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

memory: 136684kb

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

memory: 140932kb

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

memory: 137172kb

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

memory: 138792kb

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

memory: 136752kb

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

memory: 136736kb

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'