oj.uz

답안 #341091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341091 2020-12-29T01:48:40 Z ommivorous Lightning Rod (NOI18_lightningrod) C++14
19 / 100
 2000 ms 245484 KB 
/* Do what u love, love what u do */
// lightning rod 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define f first
#define s second
#define mp make_pair
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define Ford(i, r, l) for (int i = r; i > l; i--)
#define FordE(i, r, l) for (int i = r; i >= l; i--)
#define Fora(i, a) for (auto i : a)
long double pi = 3.14159265359;
const ll inf = 1e18;
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll n , res = 0;
	cin >> n;
	bool used[n+1];
	memset(used,false,sizeof(used));
	ll dp[n+1];
	vector<pair<ll,ll>> point(n);
	For(i,0,n){
		cin >> point[i].f >> point[i].s;
	}
	ForE(i,1,n){
	   used[i] = true;
	}
	sort(point.begin(),point.end());
	ll x[n+1] , y[n+1];
	For(i,0,n){
		x[i+1] = point[i].f;
		y[i+1] = point[i].s;
	}
	dp[0] = -inf;
	ForE(i,1,n){
		dp[i] = max({dp[i-1],x[i]+y[i]});
	}
	ForE(i,1,n){
		if (x[i]+y[i]<=dp[i-1]){
			used[i] = false;
		}
	}
	dp[n+1] = -inf;
	FordE(i,n,1){
		dp[i] = max({dp[i+1],y[i]-x[i]});
	}
	ForE(i,1,n){
		if (y[i]-x[i]<=dp[i+1]){
			used[i] = false;
		}
	}
	ForE(i,1,n){
		if (used[i]){
			res++;
		}
	}
	cout << res << endl;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2090 ms 245484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Incorrect 1 ms 492 KB Output isn't correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Incorrect 1 ms 492 KB Output isn't correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2077 ms 187312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2090 ms 245484 KB Time limit exceeded
2 Halted 0 ms 0 KB -