oj.uz

Submission #456382

# Submission time Handle Problem Language Result Execution time Memory
456382 2021-08-06T15:26:45 Z armand Distributing Candies (IOI21_candies) C++17
11 / 100
 5000 ms 16904 KB 
#include "candies.h"

#include <vector>
#include <algorithm>

bool all_pos(std::vector<int> v, int n)
{
	for (int i = 0; i < n; i++)
		if (v[i] < 0)
			return false;
	return true;
}

std::vector<int> solve2(std::vector<int> c, std::vector<int> l,
	std::vector<int> r, std::vector<int> v)
{
	int i;
	int n = c.size();
	std::vector<int> s(n);
	std::vector<long long> p(n + 1);
	int m = v.size();
	for (i = 0; i < n + 1; i++) p[i] = 0;
	for (i = 0; i < m; i++) {
		p[l[i]] += v[i];
		p[r[i] + 1] -= v[i];
	}
	for (i = 1; i < n + 1; i++)
		p[i] += p[i - 1];
	for (i = 0; i < n; i++)
		if (p[i] < c[i])
			s[i] = p[i];
		else
			s[i] = c[i];
	return s;
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v)
{
	int i, j;
    int n = c.size();
    std::vector<int> s(n);
	for (i = 0; i < n; i++)
		s[i] = 0;
	int m = v.size();
	if (all_pos(v, m)) {
		s = solve2(c, l, r, v);
		return s;
	}
	for (i = 0; i < m; i++) {
		if (v[i] > 0)
			for (j = l[i]; j <= r[i]; j++)
				s[j] = std::min(c[j], s[j] + v[i]);
		else
			for (j = l[i]; j <= r[i]; j++)
				s[j] = s[j] + v[i] < 0 ? 0 : s[j] + v[i];
	}
    return s;
}
/*
3
10 15 13
3
0 2 2
0 1 1
1 1 3
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 396 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 12888 KB Output is correct
2 Correct 139 ms 16904 KB Output is correct
3 Correct 121 ms 16644 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 226 ms 5712 KB Output is correct
3 Correct 225 ms 3732 KB Output is correct
4 Execution timed out 5010 ms 8024 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 577 ms 5716 KB Output is correct
4 Correct 553 ms 2796 KB Output is correct
5 Execution timed out 5050 ms 8100 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 396 KB Output is correct
6 Correct 133 ms 12888 KB Output is correct
7 Correct 139 ms 16904 KB Output is correct
8 Correct 121 ms 16644 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 226 ms 5712 KB Output is correct
11 Correct 225 ms 3732 KB Output is correct
12 Execution timed out 5010 ms 8024 KB Time limit exceeded
13 Halted 0 ms 0 KB -