oj.uz

Submission #388008

# Submission time Handle Problem Language Result Execution time Memory
388008 2021-04-09T17:49:45 Z tushar_2658 Walking (NOI12_walking) C++14
25 / 25
 1 ms 336 KB 
#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.0 / 3.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct