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

Submission #3926937

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+1], b[N+1], 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++) {
		ll mxi = -mx.second;
		if(sh[mxi].second + mnv>=0){
			sh[i] = make_pair(sh[mxi].first + i - mxi, sh[mxi].second + at[i - 1] - at[mxi - 1]);
		}
		else {
			if (mx.first == 0)sh[i].first = n + 1;
			else sh[i] = make_pair(sh[mxi].first + i - mxi + (-(sh[mxi].second+mnv)+mx.first-1) / mx.first, sh[mxi].second+at[i-1]-at[mxi-1]+((-(sh[mxi].second + 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[mxi].second+mx.first*(n-(sh[-mx.second].first+i-mxi))+at[i-1]-at[mxi-1];
		ans = max(ans, cv);
	}
	cout << max(ans,at[n]) << endl;
	return 0;
}

Submission

Task問題 D - 高橋君の旅行
User nameユーザ名 eric_endo
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1557 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 WA
00_small_sample_02.txt WA
00_small_sample_03.txt AC 1 ms 256 KB
10_small_01.txt WA
10_small_02.txt WA
10_small_03.txt AC 1 ms 256 KB
10_small_04.txt WA
10_small_05.txt WA
10_small_06.txt WA
20_large_01.txt AC 72 ms 2560 KB
20_large_02.txt WA
20_large_03.txt WA
20_large_04.txt WA
20_large_05.txt WA
20_large_06.txt WA
20_large_07.txt WA
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 AC 69 ms 4096 KB
20_large_20.txt WA
20_large_21.txt WA
20_large_22.txt WA
20_large_23.txt WA
20_large_24.txt WA
20_large_25.txt AC 69 ms 4096 KB
20_large_26.txt WA
20_large_27.txt WA
20_large_28.txt AC 70 ms 4096 KB
20_large_29.txt WA
20_large_30.txt WA
30_run_through_01.txt AC 79 ms 4096 KB
70_maximum_01.txt AC 94 ms 4096 KB
80_hand_01.txt AC 35 ms 4096 KB
80_hand_02.txt WA
80_hand_03.txt WA
80_hand_04.txt AC 34 ms 4096 KB
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 AC 1 ms 256 KB