Submission #676466

#TimeUsernameProblemLanguageResultExecution timeMemory
676466penguin133Walking (NOI12_walking)C++17
25 / 25
42 ms1236 KiB
#include <bits/stdc++.h> using namespace std; int grid[505][505]; int dp[505], maxi=1; pair<int, int>a[505]; int main(){ int l,n; cin >> l >> n; for(int i=0;i<n;i++)cin >> a[i].first >> a[i].second; sort(a, a + n); for(int i=0;i<n;i++){ grid[i][i] = 1; for(int j=0;j<n;j++){ double x = double(l)/double(a[i].second) + a[i].first; double y = double(l)/double(a[j].second) + a[j].first; if(a[i].first > a[j].first)swap(x,y); if(x > y){ grid[i][j] = 1; grid[j][i] = 1; } } } dp[n-1] = 1; for(int i=n-2;i>=0;i--){ for(int j=i+1;j<n;j++){ int cnt = 0; for(int k=j;k<n;k++){ if(grid[i][k] == 0 && grid[j][k] == 1)cnt++; } dp[i] = max(dp[i], dp[j] + 1 - cnt); } maxi = max(maxi, dp[i]); } cout << maxi; }
#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...