oj.uz

Submission #395112

# Submission time Handle Problem Language Result Execution time Memory
395112 2021-04-27T19:49:50 Z Daniel123 Lightning Rod (NOI18_lightningrod) C++14
80 / 100
 2000 ms 236472 KB 
#include <iostream>
#include <vector>

using namespace std;

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

	int n;
	cin >> n;
	int* x = new int[n];
	int* y = new int[n];
	vector<int> s;
	for (int i = 0; i < n; i++)
	{
		cin >> x[i] >> y[i];
		while (!s.empty() && x[i] - x[s.back()] <= y[i] - y[s.back()])
		{
			s.pop_back();
		}
		if (s.empty() || x[i] - x[s.back()] > y[s.back()] - y[i])
		{
			s.push_back(i);
		}
	}
	cout << s.size() << endl;
	cin >> n;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1795 ms 229488 KB Output is correct
2 Correct 1803 ms 229408 KB Output is correct
3 Correct 1732 ms 229420 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 308 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 44 ms 5320 KB Output is correct
15 Correct 46 ms 5188 KB Output is correct
16 Correct 46 ms 4952 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1826 ms 199276 KB Output is correct
2 Correct 1844 ms 198952 KB Output is correct
3 Correct 1805 ms 194236 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1795 ms 229488 KB Output is correct
2 Correct 1803 ms 229408 KB Output is correct
3 Correct 1732 ms 229420 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 44 ms 5320 KB Output is correct
18 Correct 46 ms 5188 KB Output is correct
19 Correct 46 ms 4952 KB Output is correct
20 Correct 1826 ms 199276 KB Output is correct
21 Correct 1844 ms 198952 KB Output is correct
22 Correct 1805 ms 194236 KB Output is correct
23 Execution timed out 2088 ms 236472 KB Time limit exceeded
24 Halted 0 ms 0 KB -