Submission #170353

#	Time	Username	Problem	Language	Result	Execution time	Memory
170353		ngmh	Walking (NOI12_walking)	C++11	25 / 25	6 ms	1528 KiB

walking

#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 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7