답안 #293132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293132	2020-09-07T16:42:23 Z	Saboon	고대 책들 (IOI17_books)	C++17	42 / 100	191 ms	23096 KB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000 + 10;

bool visited[maxn];
int c[maxn], l[maxn], r[maxn];

int n;
int dp[maxn][maxn], mr[maxn][maxn], ml[maxn][maxn];

long long minimum_walk(vector<int> p, int s){
	n = p.size();
	ll answer = 0;
    for (int i = 0; i < n; i++)
        answer += abs(p[i]-i);
    memset(r, -1, sizeof r);
    memset(l, 63, sizeof l);
    for (int i = 0; i < n; i++){
        if (!visited[i]){
            int x = i;
            while (!visited[x]){
                visited[x] = 1;
                c[x] = i;
                r[i] = max(r[i],x);
                l[i] = min(l[i],x);
                x = p[x];
            }
            x = p[x];
            while (x != i){
                l[x] = l[i], r[x] = r[i];
                x = p[x];
            }
        }
    }
    ml[s][s] = l[s];
    mr[s][s] = r[s];
    for (int i = s; i >= 0; i--){
        for (int j = s; j < n; j++){
            if (i == s and j == s)
                continue;
            ml[i][j] = n;
            if (i < s)
                ml[i][j] = min(l[i], ml[i+1][j]), mr[i][j] = max(r[i], mr[i+1][j]);
            if (j > s)
                ml[i][j] = min(l[j], ml[i][j-1]), mr[i][j] = max(r[j], mr[i][j-1]);
        }
    }
    memset(dp, 63, sizeof dp);
    dp[s][s] = 0;
    for (int i = s; i >= 0; i--){
        for (int j = s; j < n; j++){
            if (j < n-1)
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + (mr[i][j] <= j));
            if (i > 0)
                dp[i-1][j] = min(dp[i-1][j], dp[i][j] + (ml[i][j] >= i));
        }
    }
    int fi = s, se = s;
    for (int i = 0; i < n; i++){
        if (p[i] != i){
            fi = min(fi,i);
            se = max(se,i);
        }
    }
    dp[n][0] = 0;
	return answer + 2LL*dp[fi][se];
}

Subtask #1

12.0 / 12.0

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

Subtask #2

10.0 / 10.0

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

Subtask #3

0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4352 KB	Output is correct
2	Correct	3 ms	4352 KB	Output is correct
3	Correct	3 ms	4352 KB	Output is correct
4	Correct	3 ms	4352 KB	Output is correct
5	Correct	3 ms	4352 KB	Output is correct
6	Correct	3 ms	4352 KB	Output is correct
7	Correct	3 ms	4352 KB	Output is correct
8	Correct	3 ms	4352 KB	Output is correct
9	Correct	3 ms	4352 KB	Output is correct
10	Correct	3 ms	4352 KB	Output is correct
11	Correct	3 ms	4352 KB	Output is correct
12	Correct	3 ms	4352 KB	Output is correct
13	Correct	4 ms	4352 KB	Output is correct
14	Correct	3 ms	4352 KB	Output is correct
15	Correct	3 ms	4352 KB	Output is correct
16	Correct	3 ms	4352 KB	Output is correct
17	Correct	3 ms	4352 KB	Output is correct
18	Correct	3 ms	4352 KB	Output is correct
19	Correct	3 ms	4352 KB	Output is correct
20	Correct	3 ms	4352 KB	Output is correct
21	Correct	3 ms	4352 KB	Output is correct
22	Correct	3 ms	4352 KB	Output is correct
23	Correct	4 ms	4352 KB	Output is correct
24	Correct	3 ms	4352 KB	Output is correct
25	Correct	3 ms	4352 KB	Output is correct
26	Correct	4 ms	4352 KB	Output is correct
27	Correct	3 ms	4352 KB	Output is correct
28	Correct	3 ms	4348 KB	Output is correct
29	Correct	3 ms	4352 KB	Output is correct
30	Runtime error	191 ms	23096 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7680 KB	Output is correct
2	Correct	3 ms	4608 KB	Output is correct
3	Correct	8 ms	7424 KB	Output is correct
4	Correct	8 ms	9088 KB	Output is correct
5	Correct	7 ms	8320 KB	Output is correct
6	Correct	7 ms	7552 KB	Output is correct
7	Correct	7 ms	8320 KB	Output is correct
8	Correct	7 ms	8320 KB	Output is correct
9	Correct	8 ms	9856 KB	Output is correct
10	Correct	7 ms	12288 KB	Output is correct
11	Correct	7 ms	7936 KB	Output is correct
12	Correct	7 ms	8576 KB	Output is correct
13	Correct	7 ms	9216 KB	Output is correct
14	Correct	7 ms	7808 KB	Output is correct
15	Correct	8 ms	8832 KB	Output is correct
16	Correct	7 ms	7552 KB	Output is correct
17	Correct	7 ms	8192 KB	Output is correct
18	Correct	8 ms	8608 KB	Output is correct
19	Correct	7 ms	8064 KB	Output is correct
20	Correct	8 ms	10496 KB	Output is correct

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4352 KB	Output is correct
2	Correct	3 ms	4352 KB	Output is correct
3	Correct	3 ms	4352 KB	Output is correct
4	Correct	3 ms	4352 KB	Output is correct
5	Correct	3 ms	4352 KB	Output is correct
6	Correct	3 ms	4352 KB	Output is correct
7	Correct	3 ms	4352 KB	Output is correct
8	Correct	3 ms	4352 KB	Output is correct
9	Correct	3 ms	4352 KB	Output is correct
10	Correct	3 ms	4352 KB	Output is correct
11	Correct	3 ms	4352 KB	Output is correct
12	Correct	3 ms	4352 KB	Output is correct
13	Correct	4 ms	4352 KB	Output is correct
14	Correct	3 ms	4352 KB	Output is correct
15	Correct	3 ms	4352 KB	Output is correct
16	Correct	3 ms	4352 KB	Output is correct
17	Correct	3 ms	4352 KB	Output is correct
18	Correct	3 ms	4352 KB	Output is correct
19	Correct	3 ms	4352 KB	Output is correct
20	Correct	3 ms	4352 KB	Output is correct
21	Correct	3 ms	4352 KB	Output is correct
22	Correct	3 ms	4352 KB	Output is correct
23	Correct	4 ms	4352 KB	Output is correct
24	Correct	3 ms	4352 KB	Output is correct
25	Correct	3 ms	4352 KB	Output is correct
26	Correct	4 ms	4352 KB	Output is correct
27	Correct	3 ms	4352 KB	Output is correct
28	Correct	3 ms	4348 KB	Output is correct
29	Correct	3 ms	4352 KB	Output is correct
30	Runtime error	191 ms	23096 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-