oj.uz

Submission #917548

# Submission time Handle Problem Language Result Execution time Memory
917548 2024-01-28T11:55:31 Z 406 Walking (NOI12_walking) C++17
25 / 25
 1 ms 2904 KB 
#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;

const int64_t INF = 1ll << 30;
const int N = 2e5 + 5;

ar a[N + 5];
int n, dp[N];

bool cmp(int i, int j) {
        return a[i][0] * a[j][1] < a[j][0] * a[i][1];
}

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        int L;
        cin >> L >> n;
        FOR(i, 0, n) {
                cin >> a[i][0] >> a[i][1];
        }
        sort(a, a + n, [&](const auto A, const auto B) {return A[0] > B[0];});

        FOR(i, 0, n) {
                a[i][0] *= a[i][1];
                a[i][0] += L;
        }

        a[N] = {INF, 1};
        a[N + 1] = {-INF, 1};
        fill(dp, dp + N, N);
        dp[0] = N + 1;

        FOR(i, 0, n) {
                int x = lower_bound(dp, dp + N, i, cmp) - dp;
                dp[x] = i;
        }
        int x = 0;
        while (dp[x] != N) ++x;
        cout << --x << '\n';

        return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2516 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2512 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct