답안 #798449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
798449	2023-07-30T17:40:14 Z	PixelCat	고대 책들 (IOI17_books)	C++14	42 / 100	132 ms	56416 KB

books

#include "books.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1000;
const int INF = 1e18;

int nxtl[MAXN + 10][MAXN + 10];
int nxtr[MAXN + 10][MAXN + 10];
int ll[MAXN + 10];
int rr[MAXN + 10];
int dp[MAXN + 10][MAXN + 10];

int solve(int l, int r, int L, int R) {
    if(l < L || r > R) return INF;
    if(dp[l][r] != -1) return dp[l][r];
    if(l == L && r == R) return dp[l][r] = 0;
    if(nxtl[l][r] != l || nxtr[l][r] != r) {
        return dp[l][r] = solve(nxtl[l][r], nxtr[l][r], L, R);
    }
    int cl = l - ll[l];
    int cr = rr[r] - r;
    dp[l][r] = min(
        solve(ll[l], r, L, R) + cl * 2,
        solve(l, rr[r], L, R) + cr * 2
    );
    return dp[l][r];
}

LL minimum_walk(vector<i32> p, i32 s) {
    assert(s >= 0);
    int n = sz(p);

    int ans = 0;
    vector<int> cid(n, -1);
    vector<pii> range;
    For(i, 0, n - 1) if(p[i] != i && cid[i] == -1) {
        int cur = i;
        int l = n + 1;
        int r = -1;
        do {
            l = min(l, cur);
            r = max(r, cur);
            ans += abs(p[cur] - cur);
            cur = p[cur];
            cid[cur] = sz(range);
        } while(cur != i);
        range.eb(l, r);
    }
    if(sz(range) == 0) return 0;

    ll[0] = -1e10;
    For(i, 1, n - 1) {
        if(cid[i - 1] >= 0) ll[i] = i - 1;
        else ll[i] = ll[i - 1];
    }
    rr[n - 1] = 1e10;
    Forr(i, n - 2, 0) {
        if(cid[i + 1] >= 0) rr[i] = i + 1;
        else rr[i] = rr[i + 1];
    }

    For(i, 0, n - 1) {
        if(cid[i] >= 0) {
            nxtl[i][i] = range[cid[i]].F;
            nxtr[i][i] = range[cid[i]].S;
        } else {
            nxtl[i][i] = i;
            nxtr[i][i] = i;
        }
    }
    Forr(i, n - 1, 0) For(j, i + 1, n - 1) {
        nxtl[i][j] = min(nxtl[i][j - 1], nxtl[i + 1][j]);
        nxtr[i][j] = max(nxtr[i][j - 1], nxtr[i + 1][j]);
    }

    int L = 0, R = n - 1;
    while(cid[L] == -1) L++;
    while(cid[R] == -1) R--;
    L = min(L, (int)s);
    R = max(R, (int)s);
    cerr << L << " " << R << "\n";

    memset(dp, -1, sizeof(dp));
    return ans + solve(s, s, L, R);
}

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8276 KB	Output is correct
2	Correct	3 ms	8224 KB	Output is correct
3	Correct	3 ms	8276 KB	Output is correct
4	Correct	3 ms	8276 KB	Output is correct
5	Correct	3 ms	8276 KB	Output is correct
6	Correct	3 ms	8276 KB	Output is correct
7	Correct	3 ms	8276 KB	Output is correct
8	Correct	3 ms	8276 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	3 ms	8276 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	3 ms	8276 KB	Output is correct
13	Correct	3 ms	8276 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	3 ms	8276 KB	Output is correct
16	Correct	3 ms	8276 KB	Output is correct
17	Correct	4 ms	8276 KB	Output is correct
18	Correct	3 ms	8240 KB	Output is correct
19	Correct	10 ms	22152 KB	Output is correct
20	Correct	10 ms	22100 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	12 ms	22100 KB	Output is correct
23	Correct	10 ms	22128 KB	Output is correct
24	Correct	10 ms	22100 KB	Output is correct
25	Correct	10 ms	22216 KB	Output is correct
26	Correct	10 ms	22092 KB	Output is correct
27	Correct	10 ms	22196 KB	Output is correct
28	Correct	10 ms	22100 KB	Output is correct
29	Correct	10 ms	22100 KB	Output is correct

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8276 KB	Output is correct
2	Correct	3 ms	8224 KB	Output is correct
3	Correct	3 ms	8276 KB	Output is correct
4	Correct	3 ms	8276 KB	Output is correct
5	Correct	3 ms	8276 KB	Output is correct
6	Correct	3 ms	8276 KB	Output is correct
7	Correct	3 ms	8276 KB	Output is correct
8	Correct	3 ms	8276 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	3 ms	8276 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	3 ms	8276 KB	Output is correct
13	Correct	3 ms	8276 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	3 ms	8276 KB	Output is correct
16	Correct	3 ms	8276 KB	Output is correct
17	Correct	4 ms	8276 KB	Output is correct
18	Correct	3 ms	8240 KB	Output is correct
19	Correct	10 ms	22152 KB	Output is correct
20	Correct	10 ms	22100 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	12 ms	22100 KB	Output is correct
23	Correct	10 ms	22128 KB	Output is correct
24	Correct	10 ms	22100 KB	Output is correct
25	Correct	10 ms	22216 KB	Output is correct
26	Correct	10 ms	22092 KB	Output is correct
27	Correct	10 ms	22196 KB	Output is correct
28	Correct	10 ms	22100 KB	Output is correct
29	Correct	10 ms	22100 KB	Output is correct
30	Runtime error	132 ms	56416 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	22100 KB	Output is correct
2	Correct	10 ms	22204 KB	Output is correct
3	Correct	11 ms	22128 KB	Output is correct
4	Correct	11 ms	22196 KB	Output is correct
5	Correct	11 ms	22100 KB	Output is correct
6	Correct	10 ms	22192 KB	Output is correct
7	Correct	10 ms	22100 KB	Output is correct
8	Correct	11 ms	22204 KB	Output is correct
9	Correct	11 ms	22196 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	11 ms	22228 KB	Output is correct
12	Correct	11 ms	22268 KB	Output is correct
13	Correct	11 ms	22144 KB	Output is correct
14	Correct	10 ms	22200 KB	Output is correct
15	Correct	10 ms	22204 KB	Output is correct
16	Correct	10 ms	22100 KB	Output is correct
17	Correct	11 ms	22196 KB	Output is correct
18	Correct	10 ms	22228 KB	Output is correct
19	Correct	10 ms	22172 KB	Output is correct
20	Correct	10 ms	22100 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8276 KB	Output is correct
2	Correct	3 ms	8224 KB	Output is correct
3	Correct	3 ms	8276 KB	Output is correct
4	Correct	3 ms	8276 KB	Output is correct
5	Correct	3 ms	8276 KB	Output is correct
6	Correct	3 ms	8276 KB	Output is correct
7	Correct	3 ms	8276 KB	Output is correct
8	Correct	3 ms	8276 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	3 ms	8276 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	3 ms	8276 KB	Output is correct
13	Correct	3 ms	8276 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	3 ms	8276 KB	Output is correct
16	Correct	3 ms	8276 KB	Output is correct
17	Correct	4 ms	8276 KB	Output is correct
18	Correct	3 ms	8240 KB	Output is correct
19	Correct	10 ms	22152 KB	Output is correct
20	Correct	10 ms	22100 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	12 ms	22100 KB	Output is correct
23	Correct	10 ms	22128 KB	Output is correct
24	Correct	10 ms	22100 KB	Output is correct
25	Correct	10 ms	22216 KB	Output is correct
26	Correct	10 ms	22092 KB	Output is correct
27	Correct	10 ms	22196 KB	Output is correct
28	Correct	10 ms	22100 KB	Output is correct
29	Correct	10 ms	22100 KB	Output is correct
30	Runtime error	132 ms	56416 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

답안 #798449

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
0 / 30.0