Submission #17293

#	Time	Username	Problem	Language	Result	Execution time	Memory
17293		gs14004	Walking (NOI12_walking)	C++14	25 / 25	0 ms	1728 KiB

walking

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