답안 #486969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486969	2021-11-13T16:01:04 Z	bigDuck	Group Photo (JOI21_ho_t3)	C++14	100 / 100	859 ms	117824 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
inline char get_ (){
    const int oo=1000005;
    static char buf[oo], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, oo, stdin), p1 == p2) ? EOF : *p1 ++;
}
int read_ () {
    char c = get_();
    int sum = 0;
    while(!(c >= '0' && c <= '9')) c = get_();
    while(c >= '0' && c <= '9') sum = sum * 10 + (c - '0'), c = get_();
    return sum;
}



int n, H[5001];
int dp[5001];
int fw[5001];




void update(int i, int x){

for(int j=i; j<=n; j+=(j&(-j))){
    fw[j]+=x;
}

}

int query(int i){
int res=0;
for(int j=i; j>0; j-=(j&(-j)) ){
    res+=fw[j];
}
return res;
}

int ord[5001];
int h[5001];
int c[5001][5001];


int32_t main(){
INIT
cin>>n;
for(int i=1; i<=n; i++){
    cin>>H[i];
    //ord[H[i] ]=i;
}

for(int i=1; i<=n; i++){
    for(int j=1; j<i; j++){
        h[j]=j;
    }
    for(int j=1, cnt=i; j<=n; j++){
        if(H[j]>=i){
            h[cnt]=H[j];
            ord[h[cnt] ]=cnt;
            cnt++;
        }
    }
    for(int j=1; j<=n; j++){
        fw[j]=0;
    }


    int mn1=0;
    for(int j=i; j<=n; j++){
        int add=ord[j]+query(ord[j])-j;
        mn1+=add;
        update(i, 1);
        update(ord[j]+1, -1);
        c[i][j]=mn1;
    }


    for(int j=1; j<=n; j++){
        fw[j]=0;
    }

    int mn2=0;
    for(int j=i; j<=n; j++){
        int add=ord[j]-i-(j-i-query(ord[j]) );
        mn2+=add;
        update(ord[j], 1);
        c[i][j]=min(c[i][j], mn2);
    }

}



for(int i=1; i<=n; i++){
    dp[i]=1e18;
    for(int j=i-1; j>=0; j--){
        dp[i]=min(dp[i], dp[j]+c[j+1][i]);
    }
}

/*
for(int i=1; i<=n; i++){
    cout<<dp[i]<<" ";
}
*/
cout<<dp[n];

return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	460 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct

Subtask #3
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	460 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	2 ms	1228 KB	Output is correct
22	Correct	2 ms	1228 KB	Output is correct
23	Correct	2 ms	1228 KB	Output is correct
24	Correct	2 ms	1232 KB	Output is correct
25	Correct	2 ms	1228 KB	Output is correct
26	Correct	2 ms	1228 KB	Output is correct
27	Correct	2 ms	1228 KB	Output is correct
28	Correct	2 ms	1220 KB	Output is correct
29	Correct	2 ms	1228 KB	Output is correct
30	Correct	2 ms	1228 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	460 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	2 ms	1228 KB	Output is correct
22	Correct	2 ms	1228 KB	Output is correct
23	Correct	2 ms	1228 KB	Output is correct
24	Correct	2 ms	1232 KB	Output is correct
25	Correct	2 ms	1228 KB	Output is correct
26	Correct	2 ms	1228 KB	Output is correct
27	Correct	2 ms	1228 KB	Output is correct
28	Correct	2 ms	1220 KB	Output is correct
29	Correct	2 ms	1228 KB	Output is correct
30	Correct	2 ms	1228 KB	Output is correct
31	Correct	18 ms	6092 KB	Output is correct
32	Correct	18 ms	6056 KB	Output is correct
33	Correct	20 ms	6008 KB	Output is correct
34	Correct	18 ms	6084 KB	Output is correct
35	Correct	18 ms	6092 KB	Output is correct
36	Correct	18 ms	6116 KB	Output is correct
37	Correct	18 ms	6040 KB	Output is correct
38	Correct	19 ms	6084 KB	Output is correct
39	Correct	18 ms	6080 KB	Output is correct
40	Correct	18 ms	6084 KB	Output is correct

Subtask #5
36.0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	460 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	2 ms	1228 KB	Output is correct
22	Correct	2 ms	1228 KB	Output is correct
23	Correct	2 ms	1228 KB	Output is correct
24	Correct	2 ms	1232 KB	Output is correct
25	Correct	2 ms	1228 KB	Output is correct
26	Correct	2 ms	1228 KB	Output is correct
27	Correct	2 ms	1228 KB	Output is correct
28	Correct	2 ms	1220 KB	Output is correct
29	Correct	2 ms	1228 KB	Output is correct
30	Correct	2 ms	1228 KB	Output is correct
31	Correct	18 ms	6092 KB	Output is correct
32	Correct	18 ms	6056 KB	Output is correct
33	Correct	20 ms	6008 KB	Output is correct
34	Correct	18 ms	6084 KB	Output is correct
35	Correct	18 ms	6092 KB	Output is correct
36	Correct	18 ms	6116 KB	Output is correct
37	Correct	18 ms	6040 KB	Output is correct
38	Correct	19 ms	6084 KB	Output is correct
39	Correct	18 ms	6080 KB	Output is correct
40	Correct	18 ms	6084 KB	Output is correct
41	Correct	851 ms	117360 KB	Output is correct
42	Correct	836 ms	117316 KB	Output is correct
43	Correct	835 ms	117468 KB	Output is correct
44	Correct	837 ms	117772 KB	Output is correct
45	Correct	845 ms	117580 KB	Output is correct
46	Correct	830 ms	117580 KB	Output is correct
47	Correct	859 ms	117824 KB	Output is correct
48	Correct	824 ms	117532 KB	Output is correct
49	Correct	827 ms	117448 KB	Output is correct
50	Correct	823 ms	117392 KB	Output is correct
51	Correct	825 ms	117572 KB	Output is correct
52	Correct	843 ms	117484 KB	Output is correct
53	Correct	841 ms	117616 KB	Output is correct
54	Correct	831 ms	117480 KB	Output is correct
55	Correct	826 ms	117644 KB	Output is correct

답안 #486969

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 32.0 / 32.0

Subtask #4 20.0 / 20.0

Subtask #5 36.0 / 36.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
32.0 / 32.0

Subtask #4
20.0 / 20.0

Subtask #5
36.0 / 36.0