Submission #57611838

Source Code Expand

#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;

using ll = long long;
constexpr int N = 3e6 + 5;

int n, m, t; ll a[N], f[N], mx = 1e18;
int q[N], hh, tt;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> t;
	for(int i = 1; i <= n; ++ i) cin >> a[i];
	a[++ n] = m;
	memset(f, 0x3f, sizeof f);
	f[q[0] = 1] = a[1];
	for(int i = 2, j = 1; i <= n; ++ i) {
		while(j < i && 2 * a[j] <= 2 * a[i - 1] - t) {
			mx = min(mx, f[j] - 3 * a[j]);
			++ j;
		}
		while(hh <= tt && q[hh] < j) ++ hh;
		f[i] = mx + 2 * a[i - 1] + a[i];
		if(hh <= tt) f[i] = min(f[i], f[q[hh]] - a[q[hh]] + a[i] + t);
		while(hh <= tt && f[i] - a[i] <= f[q[tt]] - a[q[tt]]) -- tt;
		q[++ tt] = i;
	}
	cout << f[n];
	return 0;
}

Submission Info

Submission Time
Task D - Shik and Game
User Lu_xZ
Language C++ 20 (gcc 12.2)
Score 1200
Code Size 783 Byte
Status AC
Exec Time 16 ms
Memory 28192 KiB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 600 / 600 600 / 600
Status
AC × 3
AC × 23
AC × 64
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
Subtask1 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt
Case Name Status Exec Time Memory
0_00.txt AC 9 ms 27076 KiB
0_01.txt AC 9 ms 26960 KiB
0_02.txt AC 9 ms 26820 KiB
1_00.txt AC 9 ms 26968 KiB
1_01.txt AC 10 ms 26860 KiB
1_02.txt AC 10 ms 27040 KiB
1_03.txt AC 9 ms 26892 KiB
1_04.txt AC 10 ms 26884 KiB
1_05.txt AC 10 ms 26968 KiB
1_06.txt AC 9 ms 26832 KiB
1_07.txt AC 10 ms 26908 KiB
1_08.txt AC 10 ms 26832 KiB
1_09.txt AC 10 ms 26892 KiB
1_10.txt AC 10 ms 27088 KiB
1_11.txt AC 9 ms 26864 KiB
1_12.txt AC 9 ms 26820 KiB
1_13.txt AC 9 ms 26872 KiB
1_14.txt AC 9 ms 26888 KiB
1_15.txt AC 9 ms 26900 KiB
1_16.txt AC 10 ms 26964 KiB
1_17.txt AC 10 ms 26836 KiB
1_18.txt AC 9 ms 26968 KiB
1_19.txt AC 9 ms 27088 KiB
2_00.txt AC 14 ms 28124 KiB
2_01.txt AC 14 ms 28080 KiB
2_02.txt AC 14 ms 28000 KiB
2_03.txt AC 14 ms 28008 KiB
2_04.txt AC 14 ms 28088 KiB
2_05.txt AC 14 ms 27968 KiB
2_06.txt AC 15 ms 27976 KiB
2_07.txt AC 14 ms 28032 KiB
2_08.txt AC 15 ms 28044 KiB
2_09.txt AC 14 ms 27888 KiB
2_10.txt AC 15 ms 28184 KiB
2_11.txt AC 15 ms 28124 KiB
2_12.txt AC 15 ms 28020 KiB
2_13.txt AC 15 ms 28192 KiB
2_14.txt AC 15 ms 28184 KiB
2_15.txt AC 15 ms 28108 KiB
2_16.txt AC 15 ms 28000 KiB
2_17.txt AC 15 ms 28044 KiB
2_18.txt AC 15 ms 27948 KiB
2_19.txt AC 16 ms 28032 KiB
2_20.txt AC 16 ms 28000 KiB
2_21.txt AC 16 ms 27968 KiB
2_22.txt AC 16 ms 28180 KiB
2_23.txt AC 16 ms 28080 KiB
2_24.txt AC 16 ms 28020 KiB
2_25.txt AC 16 ms 28000 KiB
2_26.txt AC 16 ms 28112 KiB
2_27.txt AC 16 ms 28116 KiB
2_28.txt AC 16 ms 28088 KiB
2_29.txt AC 16 ms 28012 KiB
2_30.txt AC 16 ms 28080 KiB
2_31.txt AC 16 ms 28112 KiB
2_32.txt AC 16 ms 28004 KiB
2_33.txt AC 16 ms 28160 KiB
2_34.txt AC 16 ms 28092 KiB
2_35.txt AC 16 ms 28092 KiB
2_36.txt AC 16 ms 28048 KiB
2_37.txt AC 16 ms 27968 KiB
2_38.txt AC 16 ms 28028 KiB
2_39.txt AC 16 ms 27960 KiB
2_40.txt AC 16 ms 27932 KiB