답안 #645784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645784	2022-09-28T01:37:30 Z	kith14	Safety (NOI18_safety)	C++17	24 / 100	2000 ms	724 KB

safety

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 5e3+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], br[N], dp[2][N];
string s, s1, s2, ye = "YA", no = "TIDAK";

ll tree[2][N*4];

void build(ll l, ll r, ll idx, ll bt){
  if (l == r){
    tree[bt][idx] = dp[bt][l];
    return;
  }
  ll md = (l+r)/2;
  build(l,md,idx*2,bt);
  build(md+1,r,idx*2+1,bt);
  tree[bt][idx] = min(tree[bt][idx*2],tree[bt][idx*2+1]); 
}

ll que(ll l, ll r, ll idx, ll x, ll y, ll bt){
  if ( l > r || l > y || r < x) return 1e18;
  if (x <= l && r <= y) return tree[bt][idx];
  ll md = (l+r)/2;
  return min(que(l,md,idx*2,x,y,bt),que(md+1,r,idx*2+1,x,y,bt));
}

void input(){
  cin >> n >> m;
  repp(i,1,n) cin >> ar[i];
}

void solve(){
  ll lm = 5000;
  repp(i,0,lm){
    dp[n%2][i] = abs(i-ar[n]);
  }
  build(0,lm,1,n%2);

  repm(i,n-1,1){
    ll cur = (i)%2, pre = (i+1)%2;
    repp(j,0,lm){
      ll btl = max(0LL,j-m), btr = min(j+m,lm);
      // repp(kk,btl,btr){
      //   dp[cur][j] = min(dp[cur][j],dp[pre][kk]+abs(ar[i]-j));
      // }
      dp[cur][j] = que(0,lm,1,btl,btr,pre)+abs(ar[i]-j);
    }
    build(0,lm,1,cur);
  }

  ll ans = 1e18;
  repp(i,0,lm){
    ans = min(ans,dp[1][i]);
  }
  cout << ans << endl;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

Subtask #1
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	596 KB	Output is correct
2	Correct	6 ms	676 KB	Output is correct
3	Correct	4 ms	596 KB	Output is correct
4	Correct	1 ms	680 KB	Output is correct
5	Correct	6 ms	608 KB	Output is correct
6	Correct	5 ms	596 KB	Output is correct
7	Correct	6 ms	596 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	672 KB	Output is correct
2	Correct	11 ms	596 KB	Output is correct
3	Correct	8 ms	668 KB	Output is correct
4	Correct	11 ms	680 KB	Output is correct
5	Correct	8 ms	676 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	676 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	468 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	596 KB	Output is correct
2	Correct	6 ms	676 KB	Output is correct
3	Correct	4 ms	596 KB	Output is correct
4	Correct	1 ms	680 KB	Output is correct
5	Correct	6 ms	608 KB	Output is correct
6	Correct	5 ms	596 KB	Output is correct
7	Correct	6 ms	596 KB	Output is correct
8	Correct	9 ms	672 KB	Output is correct
9	Correct	11 ms	596 KB	Output is correct
10	Correct	8 ms	668 KB	Output is correct
11	Correct	11 ms	680 KB	Output is correct
12	Correct	8 ms	676 KB	Output is correct
13	Correct	323 ms	664 KB	Output is correct
14	Correct	256 ms	656 KB	Output is correct
15	Correct	33 ms	596 KB	Output is correct
16	Correct	400 ms	596 KB	Output is correct
17	Correct	370 ms	660 KB	Output is correct
18	Correct	310 ms	672 KB	Output is correct
19	Correct	256 ms	716 KB	Output is correct

Subtask #6
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	596 KB	Output is correct
2	Correct	6 ms	676 KB	Output is correct
3	Correct	4 ms	596 KB	Output is correct
4	Correct	1 ms	680 KB	Output is correct
5	Correct	6 ms	608 KB	Output is correct
6	Correct	5 ms	596 KB	Output is correct
7	Correct	6 ms	596 KB	Output is correct
8	Correct	9 ms	672 KB	Output is correct
9	Correct	11 ms	596 KB	Output is correct
10	Correct	8 ms	668 KB	Output is correct
11	Correct	11 ms	680 KB	Output is correct
12	Correct	8 ms	676 KB	Output is correct
13	Correct	323 ms	664 KB	Output is correct
14	Correct	256 ms	656 KB	Output is correct
15	Correct	33 ms	596 KB	Output is correct
16	Correct	400 ms	596 KB	Output is correct
17	Correct	370 ms	660 KB	Output is correct
18	Correct	310 ms	672 KB	Output is correct
19	Correct	256 ms	716 KB	Output is correct
20	Correct	129 ms	664 KB	Output is correct
21	Correct	394 ms	596 KB	Output is correct
22	Correct	212 ms	664 KB	Output is correct
23	Correct	23 ms	592 KB	Output is correct
24	Correct	302 ms	660 KB	Output is correct
25	Correct	160 ms	680 KB	Output is correct
26	Correct	421 ms	664 KB	Output is correct
27	Correct	261 ms	668 KB	Output is correct

Subtask #7
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	596 KB	Output is correct
2	Correct	6 ms	676 KB	Output is correct
3	Correct	4 ms	596 KB	Output is correct
4	Correct	1 ms	680 KB	Output is correct
5	Correct	6 ms	608 KB	Output is correct
6	Correct	5 ms	596 KB	Output is correct
7	Correct	6 ms	596 KB	Output is correct
8	Correct	9 ms	672 KB	Output is correct
9	Correct	11 ms	596 KB	Output is correct
10	Correct	8 ms	668 KB	Output is correct
11	Correct	11 ms	680 KB	Output is correct
12	Correct	8 ms	676 KB	Output is correct
13	Correct	323 ms	664 KB	Output is correct
14	Correct	256 ms	656 KB	Output is correct
15	Correct	33 ms	596 KB	Output is correct
16	Correct	400 ms	596 KB	Output is correct
17	Correct	370 ms	660 KB	Output is correct
18	Correct	310 ms	672 KB	Output is correct
19	Correct	256 ms	716 KB	Output is correct
20	Correct	129 ms	664 KB	Output is correct
21	Correct	394 ms	596 KB	Output is correct
22	Correct	212 ms	664 KB	Output is correct
23	Correct	23 ms	592 KB	Output is correct
24	Correct	302 ms	660 KB	Output is correct
25	Correct	160 ms	680 KB	Output is correct
26	Correct	421 ms	664 KB	Output is correct
27	Correct	261 ms	668 KB	Output is correct
28	Execution timed out	2061 ms	724 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #8
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	596 KB	Output is correct
2	Correct	6 ms	676 KB	Output is correct
3	Correct	4 ms	596 KB	Output is correct
4	Correct	1 ms	680 KB	Output is correct
5	Correct	6 ms	608 KB	Output is correct
6	Correct	5 ms	596 KB	Output is correct
7	Correct	6 ms	596 KB	Output is correct
8	Correct	9 ms	672 KB	Output is correct
9	Correct	11 ms	596 KB	Output is correct
10	Correct	8 ms	668 KB	Output is correct
11	Correct	11 ms	680 KB	Output is correct
12	Correct	8 ms	676 KB	Output is correct
13	Incorrect	5 ms	676 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #9
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	596 KB	Output is correct
2	Correct	6 ms	676 KB	Output is correct
3	Correct	4 ms	596 KB	Output is correct
4	Correct	1 ms	680 KB	Output is correct
5	Correct	6 ms	608 KB	Output is correct
6	Correct	5 ms	596 KB	Output is correct
7	Correct	6 ms	596 KB	Output is correct
8	Correct	9 ms	672 KB	Output is correct
9	Correct	11 ms	596 KB	Output is correct
10	Correct	8 ms	668 KB	Output is correct
11	Correct	11 ms	680 KB	Output is correct
12	Correct	8 ms	676 KB	Output is correct
13	Incorrect	5 ms	676 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

답안 #645784

Compilation message