fork download
copy 
  1. /*
  2.  * =====================================================================================
  3.  *
  4.  *       Filename:  gym101047_F.cpp
  5.  *
  6.  *    Description:  
  7.  *
  8.  *        Version:  1.0
  9.  *        Created:  07/19/2016 05:59:53 PM
  10.  *       Revision:  none
  11.  *       Compiler:  gcc
  12.  *
  13.  *         Author:  prateepm 
  14.  *   Organization:  
  15.  *
  16.  * =====================================================================================
  17.  */
  18.  
  19.  
  20. #include <bits/stdc++.h>
  21.  
  22. using namespace std;
  23.  
  24. #define LET(x,a)        ::typeid(a) x(a)
  25. #define IFOR(i,a,b)     for(LET(i,a);i!=(b);++i)
  26. #define EACH(it,v)      IFOR(it,v.begin(),v.end())
  27. #define FOR(i,a,b)      for(int i = (a); i < int(b);i++)
  28. #define REP(i,n)        FOR(i,0,n)
  29. #define SZ              size()
  30. #define PB              push_back
  31. #define PF              push_front
  32. #define V(x)            vector< x >
  33. #define two(X)          (1<<(X))
  34. #define twoL(X)         (((int64)(1))<<(X))
  35. #define contain(S,X)    (((S)&two(X))!=0)
  36. #define containL(S,X)   (((S)&twoL(X))!=0
  37. #define ALL(v)          (v).begin(),(v).end()
  38.  
  39. const double pi=acos(-1.0);
  40. const double eps=1e-11;
  41. const int INFINITE=0x3f3f3f3f;
  42. template<class T> inline void swap(T &a, T &b) { T temp = a; a = b; b = temp; }
  43. template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}
  44. template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}
  45. template<class T> inline T sqr(T x){return x*x;}
  46. typedef pair<int,int> ipair;
  47. template<class T> inline T lowbit(T n){return (n^(n-1))&n;}
  48. template<class T> inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));}
  49. template<class T> inline T gcd(T a, T b) { T c; while ( a != 0 ) { c = a; a = b%a;  b = c; } return b;}
  50. // iff gcd(a,b) == 1
  51. template<class T> inline T inv(T a, T b) { return 1 < a ? b - inv(b%a,a) * b / a : 1; }
  52. typedef V(int)          VI;
  53. typedef V(VI)           VII;
  54. typedef V(string)       VS;
  55. typedef long long       int64;
  56. typedef long double     LD;
  57. typedef pair<int,int>   PI;
  58.  
  59. //#define LocalHost
  60. const int MAXN = 2011;
  61. const int64 MAXV = (int64) 1e16 + 1LL;
  62. int64 dp[MAXN][MAXN];
  63. short vis[MAXN][MAXN];
  64. pair<int, pair<int64,int64> > raj[MAXN];
  65. bool cmp(pair<int, pair<int64, int64> > a, pair<int, pair<int64, int64> > b)
  66. {
  67. 	if (a.second.first != b.second.first) return (a.second.first < b.second.first);
  68. 	else if (a.second.second != b.second.second) return (a.second.second > b.second.second);
  69. 	else return (a.first < b.first);
  70. }
  71. inline int64 doit(int pos, int sp, int64 st, int n)
  72. {
  73. 	if(pos == n) return st;
  74. 	if (vis[pos][sp]) {
  75. 		return dp[pos][sp];
  76. 	}
  77. 	int64 t0 = MAXV, t1 = t0;
  78. 	if(st > raj[pos].second.first) {
  79. 		t0 = doit(pos+1,sp,st+raj[pos].second.second - raj[pos].second.first,n);
  80. 	}
  81. 	if(sp > 0) t1 = doit(pos+1,sp-1,st,n);
  82. 	if (t1 < t0) {
  83. 		--sp;
  84. 		dp[pos][sp] = t1;
  85. 	}
  86. 	else if(t0 < MAXV) dp[pos][sp] = t0;
  87. 	else dp[pos][sp] = MAXV;
  88. 	vis[pos][sp] = 1;
  89. 	return dp[pos][sp];
  90. }
  91. inline int solve(int testnum)
  92. {
  93. 	REP(i, 2001) REP(j, 2001) {
  94. 		dp[i][j] = MAXV;
  95. 		vis[i][j] = 0;
  96. 	}
  97. 	int n, k; int64 h; cin >> n >> h >> k;
  98. 	REP(i, n) {
  99. 		raj[i].first = i;
  100. 		cin >> raj[i].second.first >> raj[i].second.second;
  101. 	}
  102. 	sort(raj, raj + n, cmp);
  103. 	doit(0, k, h, n);
  104. 	REP(sp, k + 1) if (dp[0][sp] < MAXV) {
  105. 		printf("Y\n");
  106. 		return 0;
  107. 	}
  108. 	printf("N\n");
  109. 	return 0;
  110. }
  111. int main(int argc, char* argv[])
  112. {
  113. #ifdef LocalHost
  114.    freopen("input.txt","r",stdin);
  115.    freopen("output.txt","w",stdout);
  116. #endif
  117.    ios::sync_with_stdio( false);
  118.    int t = 1; cin >> t;
  119.    if(argc > 1) t = atoi(argv[1]);
  120.    FOR(_t,1,t+1) {
  121.      int ret = solve(_t);
  122.      if(ret == -1) break;
  123.    }
  124. #ifdef LocalHost
  125.    printf("Time taken : %.10f seconds\n", (1.0f*clock()) / CLOCKS_PER_SEC);
  126. #endif
  127.    return 0;
  128. }
Success #stdin #stdout 0.06s 43024KB
comments (?)
stdin
copy 
3
3 24 0
9 3
10 9
17 1
2 10 2
20 10
100 1
2 10 0
9 10
10 1
stdout
copy 
N
Y
Y
https://ideone.com/daYeK9
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!