Submission #873525

#TimeUsernameProblemLanguageResultExecution timeMemory
873525dsyzWalking (NOI12_walking)C++17
25 / 25
1 ms684 KiB
#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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...