Submission #218777

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
218777	2020-04-02T17:43:50 Z	gratus907	None (KOI16_gasM)	C++17	100 / 100	100 ms	4216 KB

gas

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n;
ll price[101010];
ll dist[101010];
ll next_small[101010];
ll total;
int main()
{
	cin >> n;
	for (int i = 1; i<n; i++)
	{
		ll x;
		cin >> x;
		dist[i] = dist[i-1] + x;
	}
	dist[n] = dist[n-1];
	for (int i = 0; i<n; i++)
		cin >> price[i];
	int l = 0, r = 0;
	while(l < n)
	{
		while(price[l] <= price[r])
			r++;
		for (int i = l; i<r; i++)
			next_small[i] = r;
		l = r;
	}
	for (int i = 0; i<n;)
	{
		total += (dist[next_small[i]]-dist[i])*price[i];
		i = next_small[i];
	}
	cout << total;
}

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	3448 KB	Output is correct
2	Correct	55 ms	2808 KB	Output is correct

Subtask #2

41.0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct

Subtask #3

42.0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	3448 KB	Output is correct
2	Correct	55 ms	2808 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	6 ms	384 KB	Output is correct
10	Correct	8 ms	384 KB	Output is correct
11	Correct	14 ms	768 KB	Output is correct
12	Correct	37 ms	1528 KB	Output is correct
13	Correct	99 ms	4216 KB	Output is correct
14	Correct	100 ms	4088 KB	Output is correct
15	Correct	65 ms	3452 KB	Output is correct