Submission #1026155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1026155	2024-07-17T16:05:52 Z	fv3	Feast (NOI19_feast)	C++14	4 / 100	30 ms	9404 KB

feast

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<ll> a, b;
ll res;

ll solve(ll pun)
{
	res = 0;
	ll last = -pun;
	ll seg_cnt = 0;

	for (auto n : b)
	{
		if (n > 0)
		{
			last += n;
			continue;
		}
		
		if (n < -pun)
		{
			if (last > 0)
			{
				res += last;
				seg_cnt++;
			}

			last = -pun;
		}
		else
		{
			last += n;
		}

		if (last < -pun)
			last = -pun;
	}

	if (last > 0)
	{
		res += last;
		seg_cnt++;
	}

	return seg_cnt;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll N, K;
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		ll n; cin >> n;
		if (n != 0)
			a.push_back(n);
	}
	N = a.size();

	{
		int i = 0;
		while (i < N && a[i] < 0) 
			i++;

		ll sum = 0;
		if (i < N) sum = a[i];
		for (i++; i < N; i++)
		{
			if ((a[i-1] ^ a[i]) < 0)
			{
				b.push_back(sum);
				sum = 0;
			}
			sum += a[i];
		}

		if (sum != 0)
			b.push_back(sum);

		if (b.size() && b.back() <= 0) 
			b.pop_back();
	}

	if (b.size() == 0)
	{
		cout << 0 << '\n';
		return 0;
	}

	ll l = 0ll; 
	ll r = 1000000000000000000ll;

	while (l < r)
	{
		ll c = (l + r) / 2ll;

		ll s = solve(c);

		if (s == K) l = r = c;
		if (s > K) l = c;
		if (s < K) r = c;
	}

	solve(l);
	cout << res + K * l << '\n';

	return 0;
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	7624 KB	Output is correct
2	Correct	21 ms	7928 KB	Output is correct
3	Correct	21 ms	7632 KB	Output is correct
4	Correct	24 ms	8784 KB	Output is correct
5	Correct	22 ms	8780 KB	Output is correct
6	Correct	27 ms	8124 KB	Output is correct
7	Correct	21 ms	7632 KB	Output is correct
8	Correct	21 ms	8140 KB	Output is correct
9	Correct	22 ms	8404 KB	Output is correct
10	Correct	25 ms	9020 KB	Output is correct

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	6356 KB	Output is correct
2	Correct	15 ms	7592 KB	Output is correct
3	Incorrect	20 ms	7632 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	30 ms	9404 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Incorrect	0 ms	348 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Incorrect	0 ms	348 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Incorrect	0 ms	348 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #7

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	7624 KB	Output is correct
2	Correct	21 ms	7928 KB	Output is correct
3	Correct	21 ms	7632 KB	Output is correct
4	Correct	24 ms	8784 KB	Output is correct
5	Correct	22 ms	8780 KB	Output is correct
6	Correct	27 ms	8124 KB	Output is correct
7	Correct	21 ms	7632 KB	Output is correct
8	Correct	21 ms	8140 KB	Output is correct
9	Correct	22 ms	8404 KB	Output is correct
10	Correct	25 ms	9020 KB	Output is correct
11	Correct	14 ms	6356 KB	Output is correct
12	Correct	15 ms	7592 KB	Output is correct
13	Incorrect	20 ms	7632 KB	Output isn't correct
14	Halted	0 ms	0 KB	-