Submission #197517

#	Time	Username	Problem	Language	Result	Execution time	Memory
197517		handlename	Walking (NOI12_walking)	C++17	25 / 25	3 ms	504 KiB

walking

#include <bits/stdc++.h>
using namespace std;
int lis(double arr[], int n) {
	int maxi = 0;
	int lis[n];
	for (int i = 0; i < n; i++) lis[i] = 1;
	for (int i = 1; i < n; i++) 
		for (int j = 0; j < i; j++) 
			if (arr[i] > arr[j] && lis[i] < lis[j] + 1) 
				lis[i] = lis[j] + 1; 
	for (int i = 0; i < n; i++)
		maxi = max(maxi,lis[i]); 
	return maxi; 
} 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    double l;
    int n;
    cin>>l>>n;
    vector<pair<double,double> > arr; //time,meeting?
    for (int i=0;i<n;i++){
        double t,v;
        cin>>t>>v;
        arr.push_back(make_pair(t,(l/v + t)));
    }
    sort(arr.begin(),arr.end());
    double brr[n];
    for (int i=0;i<n;i++){
        brr[i]=arr[n-1-i].second;
    }
    cout<<lis(brr,n);
}

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