Submission #917548

#	Time	Username	Problem	Language	Result	Execution time	Memory
917548		406	Walking (NOI12_walking)	C++17	25 / 25	1 ms	2904 KiB

walking

#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 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7