oj.uz

Submission #873525

# Submission time Handle Problem Language Result Execution time Memory
873525 2023-11-15T09:00:33 Z dsyz Walking (NOI12_walking) C++17
25 / 25
 1 ms 684 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
  ios_base::sync_with_stdio(false);cin.tie(0);
  ll L,N;
  cin>>L>>N;
  ll sum = 0;
  pair<long double,long double> arr[N];
  for(ll i = 0;i < N;i++){
    ll t,speed;
    cin>>t>>speed;
    arr[i] = make_pair(t,speed);
  }
  sort(arr,arr + N);
  ll memo[N];
  memset(memo,0,sizeof(memo));
  for(ll i = 0;i < N;i++){
    memo[i] = 1;
    for(ll j = 0;j < i;j++){
      if((L / arr[j].second) + arr[j].first > (L / arr[i].second) + arr[i].first){
        memo[i] = max(memo[i],memo[j] + 1);
      }
    }
    sum = max(sum,memo[i]);
  }
  cout<<sum<<'\n';
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 460 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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