답안 #668598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668598	2022-12-04T08:28:13 Z	600Mihnea	Lightning Rod (NOI18_lightningrod)	C++17	80 / 100	2000 ms	148828 KB

lightningrod

#include <bits/stdc++.h>


using namespace std;

struct T
{
  int x;
  int y;
};

bool good(T a, T b)
{
  return a.x <= b.x && a.y <= b.y;
}

bool operator < (T a, T b)
{
  if (a.y == b.y)
  {
    return a.x < b.x;
  }
  return a.y < b.y;
}

const int N = 10000000 + 7;
int n;
T v[N];
int dp[N];

signed main()
{
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#endif // ONPC

#ifndef ONPC
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC


  ///gen();

  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    int x, y;
    cin >> v[i].x >> v[i].y;
    x = -(v[i].x + v[i].y);
    y = (v[i].x - v[i].y);
    v[i].x = x;
    v[i].y = y;
  }

  sort(v + 1, v + n + 1);

  int mn = v[1].x, cnt = 1;

  for (int i = 2; i <= n; i++)
  {
    if (v[i].x < mn)
    {
      mn = v[i].x;
      cnt++;
    }
  }
  cout << cnt << "\n";
  return 0;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1505 ms	94968 KB	Output is correct
2	Correct	1473 ms	94572 KB	Output is correct
3	Correct	1450 ms	92108 KB	Output is correct

Subtask #2

7.0 / 7.0

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

Subtask #3

12.0 / 12.0

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

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	328 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	328 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	48 ms	5308 KB	Output is correct
15	Correct	47 ms	5300 KB	Output is correct
16	Correct	36 ms	4488 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1543 ms	94348 KB	Output is correct
2	Correct	1511 ms	94192 KB	Output is correct
3	Correct	1488 ms	91844 KB	Output is correct

Subtask #7

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1505 ms	94968 KB	Output is correct
2	Correct	1473 ms	94572 KB	Output is correct
3	Correct	1450 ms	92108 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	48 ms	5308 KB	Output is correct
18	Correct	47 ms	5300 KB	Output is correct
19	Correct	36 ms	4488 KB	Output is correct
20	Correct	1543 ms	94348 KB	Output is correct
21	Correct	1511 ms	94192 KB	Output is correct
22	Correct	1488 ms	91844 KB	Output is correct
23	Execution timed out	2062 ms	148828 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-