Submission #2406845


Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;
int n, c, a[100009], b[100009], pos[100009]; long long cost[100009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	if (b[0] == 0) {
		cout << 0 << "\n";
	}
	else {
		c = 1;
		for (int i = 0; i < n; i++) {
			if (i != 0) cost[c - 1] -= a[i - 1];
			if (b[pos[c - 1]] < b[i]) {
				pos[c++] = i;
			}
		}
		pos[c] = n;
		long long turn = 0, cur = 0, ret = 0;
		for (int i = 0; i < c; i++) {
			ret = max(ret, cur + b[pos[i]] * (n - turn));
			long long ncur = cur;
			for (int j = pos[i]; j <= pos[i + 1] && n - turn - j + pos[i] >= 0; j++) {
				ret = max(ret, ncur + b[pos[i]] * (n - turn - j + pos[i]));
				ncur += a[j];
			}
			if (cost[i] < 0) cur -= cost[i];
			else if (cost[i] > cur) {
				long long nxt_turn = (cost[i] - cur + b[pos[i]] - 1) / b[pos[i]];
				cur += nxt_turn * b[pos[i]];
				cur -= cost[i];
				turn += nxt_turn;
			}
			else cur -= cost[i];
			turn += pos[i + 1] - pos[i];
			if (turn > n) break;
		}
		cout << ret << "\n";
	}
	return 0;
}

Submission Info

Submission Time
Task D - 高橋君の旅行
User square1001
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1182 Byte
Status WA
Exec Time 22 ms
Memory 1152 KB

Judge Result

Set Name Small All
Score / Max Score 0 / 3 0 / 197
Status
AC × 10
WA × 3
AC × 40
WA × 9
Set Name Test Cases
Small 00_small_sample_00.txt, 00_small_sample_01.txt, 00_small_sample_02.txt, 00_small_sample_03.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 90_small_teuchi_00.txt, 90_small_teuchi_01.txt, 90_small_teuchi_02.txt
All 00_small_sample_00.txt, 00_small_sample_01.txt, 00_small_sample_02.txt, 00_small_sample_03.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 20_large_01.txt, 20_large_02.txt, 20_large_03.txt, 20_large_04.txt, 20_large_05.txt, 20_large_06.txt, 20_large_07.txt, 20_large_08.txt, 20_large_09.txt, 20_large_10.txt, 20_large_11.txt, 20_large_12.txt, 20_large_13.txt, 20_large_14.txt, 20_large_15.txt, 20_large_16.txt, 20_large_17.txt, 20_large_18.txt, 20_large_19.txt, 20_large_20.txt, 20_large_21.txt, 20_large_22.txt, 20_large_23.txt, 20_large_24.txt, 20_large_25.txt, 20_large_26.txt, 20_large_27.txt, 20_large_28.txt, 20_large_29.txt, 20_large_30.txt, 30_run_through_01.txt, 70_maximum_01.txt, 80_hand_01.txt, 80_hand_02.txt, 80_hand_03.txt, 80_hand_04.txt, 90_small_teuchi_00.txt, 90_small_teuchi_01.txt, 90_small_teuchi_02.txt
Case Name Status Exec Time Memory
00_small_sample_00.txt AC 1 ms 256 KB
00_small_sample_01.txt AC 1 ms 256 KB
00_small_sample_02.txt AC 1 ms 256 KB
00_small_sample_03.txt WA 1 ms 256 KB
10_small_01.txt AC 1 ms 256 KB
10_small_02.txt AC 1 ms 256 KB
10_small_03.txt AC 1 ms 256 KB
10_small_04.txt AC 1 ms 256 KB
10_small_05.txt AC 2 ms 256 KB
10_small_06.txt AC 1 ms 256 KB
20_large_01.txt AC 20 ms 1024 KB
20_large_02.txt AC 22 ms 1024 KB
20_large_03.txt AC 22 ms 1024 KB
20_large_04.txt AC 20 ms 1024 KB
20_large_05.txt AC 22 ms 1024 KB
20_large_06.txt AC 22 ms 1024 KB
20_large_07.txt AC 20 ms 1024 KB
20_large_08.txt AC 22 ms 1024 KB
20_large_09.txt AC 22 ms 1024 KB
20_large_10.txt WA 20 ms 1024 KB
20_large_11.txt WA 22 ms 1024 KB
20_large_12.txt WA 22 ms 1024 KB
20_large_13.txt AC 18 ms 1152 KB
20_large_14.txt AC 20 ms 1024 KB
20_large_15.txt AC 20 ms 1024 KB
20_large_16.txt WA 18 ms 1024 KB
20_large_17.txt AC 20 ms 1024 KB
20_large_18.txt AC 20 ms 1024 KB
20_large_19.txt AC 19 ms 1024 KB
20_large_20.txt AC 21 ms 1024 KB
20_large_21.txt AC 21 ms 1024 KB
20_large_22.txt AC 17 ms 1024 KB
20_large_23.txt AC 19 ms 1024 KB
20_large_24.txt AC 19 ms 1024 KB
20_large_25.txt AC 19 ms 1024 KB
20_large_26.txt AC 21 ms 1024 KB
20_large_27.txt AC 21 ms 1024 KB
20_large_28.txt AC 19 ms 1024 KB
20_large_29.txt AC 21 ms 1024 KB
20_large_30.txt AC 21 ms 1024 KB
30_run_through_01.txt AC 20 ms 1024 KB
70_maximum_01.txt AC 22 ms 1024 KB
80_hand_01.txt AC 13 ms 1024 KB
80_hand_02.txt WA 13 ms 1024 KB
80_hand_03.txt WA 13 ms 1024 KB
80_hand_04.txt AC 13 ms 1024 KB
90_small_teuchi_00.txt WA 1 ms 256 KB
90_small_teuchi_01.txt AC 1 ms 256 KB
90_small_teuchi_02.txt WA 1 ms 256 KB