Submission #873525

#	Time	Username	Problem	Language	Result	Execution time	Memory
873525		dsyz	Walking (NOI12_walking)	C++17	25 / 25	1 ms	684 KiB

walking

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