京都大学プログラミングコンテスト2015

Submission #535220

Source codeソースコード

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	int64_t n;
	scanf("%lld", &n);

	vector<int64_t> a(n);
	vector<int64_t> b(n);

	for (auto &it : a) scanf("%lld", &it);
	for (auto &it : b) scanf("%lld", &it);

	vector<int64_t> day(n+1, -1), rest(n+1, -1);
	day[0] = 0;
	rest[0] = 0;

	int64_t prev_max = 0;
	for (int i = 0; i <= n; i++) {
		if (i > 0) {
			if (rest[i - 1] + a[i - 1] >= 0) {
				day[i] = day[i - 1] + 1;
				rest[i] = rest[i - 1] + a[i - 1];
			}
			else {
				int64_t husoku = rest[i - 1] + a[i - 1];
				if (prev_max == 0)
					break;
				int64_t work = (-husoku + prev_max - 1	) / prev_max;
				husoku += prev_max * work;
				day[i] = day[i - 1] + work + 1;
				rest[i] = husoku;
			}
		}
		if (i < n)
			prev_max = max(prev_max, b[i]);
	}

	int64_t ans = 0;
	prev_max = 0;
	for (int i = 0; i <= n; i++) {
		if (i < n)
			prev_max = max(prev_max, b[i]);
		if (day[i] < 0) continue;
		int64_t rest_days = n - day[i];
		if (rest_days < 0) continue;
		int64_t cur = rest[i] + rest_days * prev_max;
		// cout << i << ": " << day[i] << ", " << rest[i] << ", " << cur << endl;
		ans = max(ans, cur);
	}

	cout << ans << endl;

	return 0;
}

Submission

Task問題 D - 高橋君の旅行
User nameユーザ名 tanakh
Created time投稿日時
Language言語 C++11 (GCC 4.9.2)
Status状態 AC
Score得点 200
Source lengthソースコード長 1276 Byte
File nameファイル名
Exec time実行時間 80 ms
Memory usageメモリ使用量 4064 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:10:18: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t* {aka long int*}’ [-Wformat=]
scanf("%lld", &n);
^
./Main.cpp:15:38: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘long int*’ [-Wformat=]
for (auto &it : a) scanf("%lld", &it);
^
./Main.cpp:16:38: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘long int*’ [-Wformat=]
for (auto &it : b) scanf("%lld", &it);
^
./Main.cpp:10:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
^
./Main.cpp:15:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunuse...

Test case

Set

Set name Score得点 / Max score Cases
Small 3 / 3 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 197 / 197 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_small_sample_00.txt AC 38 ms 804 KB
00_small_sample_01.txt AC 41 ms 856 KB
00_small_sample_02.txt AC 26 ms 928 KB
00_small_sample_03.txt AC 26 ms 920 KB
10_small_01.txt AC 27 ms 916 KB
10_small_02.txt AC 27 ms 812 KB
10_small_03.txt AC 27 ms 804 KB
10_small_04.txt AC 26 ms 924 KB
10_small_05.txt AC 27 ms 928 KB
10_small_06.txt AC 27 ms 928 KB
20_large_01.txt AC 75 ms 4008 KB
20_large_02.txt AC 77 ms 4004 KB
20_large_03.txt AC 78 ms 4000 KB
20_large_04.txt AC 74 ms 4000 KB
20_large_05.txt AC 76 ms 4008 KB
20_large_06.txt AC 80 ms 4000 KB
20_large_07.txt AC 76 ms 3876 KB
20_large_08.txt AC 80 ms 4008 KB
20_large_09.txt AC 79 ms 4004 KB
20_large_10.txt AC 71 ms 4000 KB
20_large_11.txt AC 77 ms 3932 KB
20_large_12.txt AC 77 ms 4004 KB
20_large_13.txt AC 67 ms 3996 KB
20_large_14.txt AC 74 ms 3936 KB
20_large_15.txt AC 72 ms 4004 KB
20_large_16.txt AC 68 ms 4064 KB
20_large_17.txt AC 76 ms 3884 KB
20_large_18.txt AC 72 ms 4004 KB
20_large_19.txt AC 72 ms 3996 KB
20_large_20.txt AC 75 ms 4000 KB
20_large_21.txt AC 73 ms 4000 KB
20_large_22.txt AC 66 ms 3996 KB
20_large_23.txt AC 74 ms 3948 KB
20_large_24.txt AC 77 ms 4008 KB
20_large_25.txt AC 71 ms 4000 KB
20_large_26.txt AC 74 ms 4004 KB
20_large_27.txt AC 74 ms 3996 KB
20_large_28.txt AC 71 ms 4004 KB
20_large_29.txt AC 75 ms 4008 KB
20_large_30.txt AC 74 ms 4004 KB
30_run_through_01.txt AC 75 ms 4008 KB
70_maximum_01.txt AC 76 ms 4008 KB
80_hand_01.txt AC 56 ms 4056 KB
80_hand_02.txt AC 57 ms 3872 KB
80_hand_03.txt AC 59 ms 4012 KB
80_hand_04.txt AC 60 ms 4004 KB
90_small_teuchi_00.txt AC 29 ms 800 KB
90_small_teuchi_01.txt AC 25 ms 928 KB
90_small_teuchi_02.txt AC 27 ms 808 KB