oj.uz

Submission #17293

# Submission time Handle Problem Language Result Execution time Memory
17293 2015-11-14T17:27:43 Z gs14004 Walking (NOI12_walking) C++14
25 / 25
 0 ms 1728 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int dp[505], l, n;
pi a[505];

bool ok(int p, int q){
	return (a[p].first < a[q].first) && 
	(l * a[q].second + a[p].first * a[p].second * a[q].second > l * a[p].second + a[q].first * a[p].second * a[q].second);
}

int main(){
	scanf("%d %d",&l,&n);
	for(int i=0; i<n; i++){
		scanf("%d %d",&a[i].first, &a[i].second);
	}
	sort(a, a+n);
	for(int i=n-1; i>=0; i--){
		dp[i] = 1;
		for(int j=i+1; j<n; j++){
			if(ok(i,j)) dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	printf("%d",*max_element(dp, dp+n));
}

Subtask #1
3.0 / 3.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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