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

Submission #3926800

Source codeソースコード

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;
const ll MOD = 1000000007,N= 100000;

ll mn(ll a, ll b) {
	if (a == -1)return b;
	if (b == -1)return a;
	return min(a, b);
}
struct ab {
	ll a, b;
	bool operator<(const ab& right) const {
		return right.b*a - right.a*b < 0;
	}
};

ll n, a[N], b[N], ans = 0, at[N+1],mnv=0,monv=0;
pos mx,sh[N+1];//days money

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) { cin >> a[i]; at[i] = at[i - 1] + a[i]; }
	for (int i = 1; i <= n; i++)cin >> b[i];
	ans = b[1] * n;
	sh[1] = make_pair(0, 0);
	mx = make_pair(b[1], -1);
	monv = a[1]; mnv = min((ll)0, a[1]);
	for (ll i = 2; i <= n+1; i++) {
		if(sh[-mx.second].first + mnv>=0){
			sh[i] = make_pair(sh[-mx.second].first + i - (-mx.second), sh[-mx.second].second + at[i - 1] - at[-mx.second - 1]);
		}
		else {
			if (mx.first == 0)sh[i].first = n + 1;
			else sh[i] = make_pair(sh[-mx.second].first + i - (-mx.second) + (-(sh[-mx.second].first+mnv)+mx.first-1) / mx.first, sh[-mx.second].second+at[i-1]-at[-mx.second-1]+((-(sh[-mx.second].first + mnv) + mx.first - 1) / mx.first)*mx.first);
		}
		if (sh[i].first >= n)break;
		mx = max(mx, make_pair(b[i], -i));
		if (mx.second == -i) { monv = 0; mnv = 0; }
		monv += a[i];
		mnv = min(monv, mnv);
		ll cv = sh[-mx.second].second+mx.first*(n-(sh[-mx.second].first+i-(-mx.second)))+at[i-1]-at[-mx.second-1];
		ans = max(ans, cv);
	}
	cout << ans << endl;
	return 0;
}

Submission

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

Test case

Set

Set name Score得点 / Max score Cases
Small 0 / 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 0 / 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 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 AC 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 1 ms 256 KB
10_small_06.txt AC 1 ms 256 KB
20_large_01.txt AC 72 ms 2560 KB
20_large_02.txt WA
20_large_03.txt WA
20_large_04.txt AC 72 ms 2560 KB
20_large_05.txt WA
20_large_06.txt WA
20_large_07.txt AC 72 ms 2560 KB
20_large_08.txt WA
20_large_09.txt WA
20_large_10.txt WA
20_large_11.txt WA
20_large_12.txt WA
20_large_13.txt WA
20_large_14.txt WA
20_large_15.txt WA
20_large_16.txt WA
20_large_17.txt WA
20_large_18.txt WA
20_large_19.txt WA
20_large_20.txt AC 82 ms 4096 KB
20_large_21.txt AC 82 ms 4096 KB
20_large_22.txt AC 58 ms 4096 KB
20_large_23.txt AC 70 ms 4096 KB
20_large_24.txt AC 70 ms 4096 KB
20_large_25.txt WA
20_large_26.txt AC 81 ms 4096 KB
20_large_27.txt AC 82 ms 4096 KB
20_large_28.txt WA
20_large_29.txt AC 81 ms 4096 KB
20_large_30.txt AC 81 ms 4096 KB
30_run_through_01.txt WA
70_maximum_01.txt RE
80_hand_01.txt AC 18 ms 1792 KB
80_hand_02.txt WA
80_hand_03.txt WA
80_hand_04.txt RE
90_small_teuchi_00.txt AC 1 ms 256 KB
90_small_teuchi_01.txt AC 1 ms 256 KB
90_small_teuchi_02.txt WA