oj.uz

Submission #170353

# Submission time Handle Problem Language Result Execution time Memory
170353 2019-12-24T20:25:41 Z ngmh Walking (NOI12_walking) C++11
25 / 25
 6 ms 1528 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, long long> pi;
typedef pair<long double, long long> pii;

long long l, n, t, v;
int dp[501][501];
pi d[501];
pii a[501];

int lcs(int al, int bl){
        if(al == 0 || bl == 0) return 0;
        if(dp[al][bl] != -1) return dp[al][bl];
        dp[al][bl] = max(lcs(al-1, bl), lcs(al, bl-1));
        if(d[al-1].second == a[bl-1].second) dp[al][bl] = max(dp[al][bl], lcs(al, bl-1)+1);
        return dp[al][bl];
}

int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        memset(dp, -1, sizeof(dp));
        cin >> l >> n;
        for(int i = 0; i < n; i++){
                cin >> t >> v;
                d[i] = pi(t, i);
                a[i] = pii((long double)t+((long double)l/(long double)v), i);
        }
        sort(d, d+n);
        sort(a, a+n);
        reverse(a, a+n);
        cout << lcs(n, n);
}

Subtask #1
3.0 / 3.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 3 ms 1276 KB Output is correct
4 Correct 4 ms 1528 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1400 KB Output is correct
2 Correct 5 ms 1400 KB Output is correct
3 Correct 5 ms 1400 KB Output is correct
4 Correct 5 ms 1400 KB Output is correct