oj.uz

Submission #345042

# Submission time Handle Problem Language Result Execution time Memory
345042 2021-01-06T23:51:37 Z nishuz Lightning Rod (NOI18_lightningrod) C++14
44 / 100
 2000 ms 183276 KB 
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, ans = 0, subtask = 1;
    cin >> n;
    vector <pair <int, int>> a(n);
    bool vis[n], ok = 1;
    memset(vis, 0, sizeof vis);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i].first >> a[i].second;
        ok &= (a[i].second == 1);
        if (i) subtask += (a[i].first != a[i-1].first);
    }
    if (ok)
    {
        cout << subtask << '\n';
        return 0;
    }
    sort(a.begin(), a.end(), [&](pair <int, int>& a, pair <int, int>& b) {return a.second > b.second;});
    for (int i = 0; i < n; ++i)
    {
        if (vis[i]) continue;
        ++ans;
        for (int j = 0; j < n; ++j) if (abs(a[i].first - a[j].first) <= abs(a[i].second - a[j].second)) vis[j] = 1;
    }
    cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1660 ms 85740 KB Output is correct
2 Correct 1695 ms 183276 KB Output is correct
3 Correct 1654 ms 179084 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 3 ms 364 KB Output is correct
13 Correct 7 ms 364 KB Output is correct
14 Correct 340 ms 1900 KB Output is correct
15 Correct 239 ms 2028 KB Output is correct
16 Execution timed out 2076 ms 1900 KB Time limit exceeded

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2094 ms 88044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1660 ms 85740 KB Output is correct
2 Correct 1695 ms 183276 KB Output is correct
3 Correct 1654 ms 179084 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 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 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 3 ms 364 KB Output is correct
16 Correct 7 ms 364 KB Output is correct
17 Correct 340 ms 1900 KB Output is correct
18 Correct 239 ms 2028 KB Output is correct
19 Execution timed out 2076 ms 1900 KB Time limit exceeded