Submission #388008

#	Time	Username	Problem	Language	Result	Execution time	Memory
388008		tushar_2658	Walking (NOI12_walking)	C++14	25 / 25	1 ms	336 KiB

walking

#include "bits/stdc++.h"
using namespace std;

const int maxn = 505;

int l, n;

struct DATA {
  int t, v;
  double x;
};

DATA p[maxn];
int dp[maxn];

int main(int argc, char const *argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> l >> n;
  for(int i = 1; i <= n; ++i){
    cin >> p[i].t >> p[i].v;
    p[i].x = (double)(l / (double)p[i].v) + (double)p[i].t;
  }
  sort(p + 1, p + n + 1, [&](DATA x, DATA y){
    if(x.t == y.t)return x.x > y.x;
    else return x.t < y.t;
  });
  int ans = 0;
  for(int i = 1; i <= n; ++i){
    dp[i] = 1;
    for(int j = 1; j < i; ++j){
      if(p[j].x > p[i].x){
        dp[i] = max(dp[i], dp[j] + 1);
      }
    }
    ans = max(ans, dp[i]);
  }
  cout << ans << '\n';

  return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7