Submission #877998

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
877998	2023-11-24 01:57:14	khoquennguoiminhthuong	Safety (NOI18_safety)	C++14	40 / 100	301 ms	197712 KiB

safety

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int n;
int lim;
int a[200005];
namespace sub12567
{
long long dp[5005][5005];
void solve()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=5000;j++)
dp[i][j]=1e18;
for(int i=0;i<=5000;i++)dp[1][i]=abs(a[1]-i);
for(int i=2;i<=n;i++)
{
deque<int>dq;
int dd=0;
for(int j=0;j<=5000;j++)
{
int l=max(0,j-lim),r=min(5000,j+lim);
while(dd<=r)
{
while(dq.size()&&dp[i-1][dq.back()]>=dp[i-1][dd])dq.pop_back();
dq.push_back(dd);
dd++;
}
while(dq.size()&&dq.front()<l)dq.pop_front();
if(dq.size())dp[i][j]=dp[i-1][dq.front()]+abs(a[i]-j);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29