답안 #942901

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942901 2024-03-11T06:40:48 Z artixkrishna 걷기 (NOI12_walking) C++14
25 / 25
1 ms 2652 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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
# 결과 실행 시간 메모리 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