oj.uz

Submission #197517

# Submission time Handle Problem Language Result Execution time Memory
197517 2020-01-21T13:29:30 Z handlename Walking (NOI12_walking) C++17
25 / 25
 3 ms 504 KB 
#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.0 / 3.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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