답안 #987179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
987179	2024-05-22T08:21:49 Z	AdamGS	고대 책들 (IOI17_books)	C++17	42 / 100	81 ms	23916 KB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e9+7;
const int LIM=1e3+7;
ll F[LIM], mi[LIM], ma[LIM], dp[LIM][LIM], dpma[LIM][LIM], dpmi[LIM][LIM], l, r;
ll fnd(ll x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
  if(fnd(a)==fnd(b)) return;
  ma[fnd(a)]=max(ma[fnd(a)], ma[fnd(b)]);
  mi[fnd(a)]=min(mi[fnd(a)], mi[fnd(b)]);
  F[fnd(b)]=fnd(a);
}
ll minimum_walk(vector<int>p, int s) {
  ll n=p.size();
  rep(i, n) F[i]=ma[i]=mi[i]=i;
  rep(i, n) uni(i, p[i]);
  l=0; r=n-1;
  while(l<s && p[l]==l) ++l;
  while(r>s && p[r]==r) --r;
  rep(i, n) {
    dpma[i][i]=ma[fnd(i)];
    dpmi[i][i]=mi[fnd(i)];
    for(int j=i+1; j<n; ++j) {
      dpma[i][j]=max(dpma[i][j-1], ma[fnd(j)]);
      dpmi[i][j]=min(dpmi[i][j-1], mi[fnd(j)]);
    }
  }
  ll ans=0;
  rep(i, n) ans+=abs(p[i]-i);
  for(ll d=r-l; d>0; --d) {
    for(ll a=l; a+d-1<=r; ++a) {
      ll b=a+d-1;
      if(dpmi[a][b]<a) dp[a][b]=dp[a-1][b];
      else if(dpma[a][b]>b) dp[a][b]=dp[a][b+1];
      else if(a==l) dp[a][b]=dp[a][b+1]+2;
      else if(b==r) dp[a][b]=dp[a-1][b]+2;
      else dp[a][b]=min(dp[a-1][b], dp[a][b+1])+2;
    }
  }
  return ans+dp[s][s];
}

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2512 KB	Output is correct
6	Correct	1 ms	2392 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2476 KB	Output is correct
9	Correct	1 ms	2392 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2496 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2464 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	11 ms	21852 KB	Output is correct
20	Correct	13 ms	21852 KB	Output is correct
21	Correct	5 ms	14940 KB	Output is correct
22	Correct	16 ms	22620 KB	Output is correct
23	Correct	15 ms	22616 KB	Output is correct
24	Correct	13 ms	23328 KB	Output is correct
25	Correct	12 ms	23128 KB	Output is correct
26	Correct	10 ms	23132 KB	Output is correct
27	Correct	9 ms	23240 KB	Output is correct
28	Correct	8 ms	23644 KB	Output is correct
29	Correct	8 ms	23708 KB	Output is correct

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2512 KB	Output is correct
6	Correct	1 ms	2392 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2476 KB	Output is correct
9	Correct	1 ms	2392 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2496 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2464 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	11 ms	21852 KB	Output is correct
20	Correct	13 ms	21852 KB	Output is correct
21	Correct	5 ms	14940 KB	Output is correct
22	Correct	16 ms	22620 KB	Output is correct
23	Correct	15 ms	22616 KB	Output is correct
24	Correct	13 ms	23328 KB	Output is correct
25	Correct	12 ms	23128 KB	Output is correct
26	Correct	10 ms	23132 KB	Output is correct
27	Correct	9 ms	23240 KB	Output is correct
28	Correct	8 ms	23644 KB	Output is correct
29	Correct	8 ms	23708 KB	Output is correct
30	Runtime error	81 ms	22956 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Subtask #4
20.0 / 20.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2512 KB	Output is correct
6	Correct	1 ms	2392 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2476 KB	Output is correct
9	Correct	1 ms	2392 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2496 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2464 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	11 ms	21852 KB	Output is correct
20	Correct	13 ms	21852 KB	Output is correct
21	Correct	5 ms	14940 KB	Output is correct
22	Correct	16 ms	22620 KB	Output is correct
23	Correct	15 ms	22616 KB	Output is correct
24	Correct	13 ms	23328 KB	Output is correct
25	Correct	12 ms	23128 KB	Output is correct
26	Correct	10 ms	23132 KB	Output is correct
27	Correct	9 ms	23240 KB	Output is correct
28	Correct	8 ms	23644 KB	Output is correct
29	Correct	8 ms	23708 KB	Output is correct
30	Runtime error	81 ms	22956 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

답안 #987179

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