Submission #548984

#	Time	Username	Problem	Language	Result	Execution time	Memory
548984		AbdelmagedNour	Walking (NOI12_walking)	C++17	25 / 25	1 ms	328 KiB

walking

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int l,n;
    cin>>l>>n;
    int dp[n]={1};
    pair<int,int>a[n];
    for(int i=0;i<n;i++)cin>>a[i].first>>a[i].second;
    sort(a,a+n,greater<pair<int,int>>());
    for(int i=1;i<n;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            long long ti=a[i].first,vi=a[i].second;
            long long tj=a[j].first,vj=a[j].second;
            if(l*vj+ti*vi*vj>l*vi+tj*vi*vj)dp[i]=max(dp[i],1+dp[j]);
        }
    }
    cout<<*max_element(dp,dp+n);
    return 0;
}

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