fork(4) download
copy 
  1. #include<iostream>
  2. #include<fstream>
  3. #include<sstream>
  4. #include<cstdio>
  5. #include<stdlib.h>
  6. #include<string>
  7. #include<cstring>
  8. #include<cmath>
  9. #include<algorithm>
  10. #include<stack>
  11. #include<queue>
  12. #include<vector>
  13. #include<utility>
  14. #include<set>
  15. #include<map>
  16. #include<iomanip>
  17.  
  18. using namespace std;
  19.  
  20. typedef long long ll;
  21. typedef string str;
  22. typedef unsigned long long ull;
  23. typedef pair<int,int> pa;
  24. typedef vector<ll> vin;
  25. typedef vector<string> vs;
  26. typedef vector<vector<ll> > vvin;
  27.  
  28. #define REP(i,a,b) for(ll i=a;i<b;i++)
  29. #define rep(i,n) REP(i,0,n)
  30. #define BREP(i,a,b) for(ll i=a-1;i>=b;i--)
  31. #define brep(i,n) BREP(i,n,0)
  32. #define pb push_back
  33. #define inf 999999999
  34. #define SIZE 10000
  35. #define mp make_pair
  36. #define sz size()
  37. #define NIL 0
  38. #define DEBUG 0
  39. #define all(vec) (vec).begin(),(vec).end()
  40. #define NEG -1
  41.  
  42. vin heights(SIZE,NIL),ret(SIZE,NIL),predecessors(SIZE,NEG);
  43. int last_boss;
  44.  
  45. void init() {
  46.     rep(i,SIZE) {
  47. 		ret[i]=1;
  48. 		predecessors[i]=NEG;
  49. 	}
  50. 	last_boss=NEG;
  51. }
  52.  
  53. void solve(int syze) {
  54. 	int max_len=NIL;
  55. 	vin temp;
  56. 	rep(i,syze)
  57. 		rep(j,i) {
  58. 			if(ret[j]+1>ret[i] && heights[j]<heights[i]) {
  59. 				ret[i]=ret[j]+1;
  60. 				predecessors[i]=j;
  61. 			}
  62. 		}
  63. 	rep(i,syze)
  64. 		if(max_len<ret[i]) {
  65. 			last_boss=i;
  66. 			max_len=ret[i];
  67. 	}
  68. 	cout<<max_len;
  69. 	while(last_boss!=-1) {
  70. 		temp.pb(heights[last_boss]);
  71. 		last_boss=predecessors[last_boss];
  72. 	}
  73. 	brep(i,temp.sz)
  74. 		cout<<"\n"<<temp[i];
  75. }
  76.  
  77. int main() {
  78. 	int test_cases,height,index;
  79. 	stringstream ss;
  80. 	str str1;
  81. 	getline(cin,str1);
  82. 	ss<<str1;
  83. 	ss>>test_cases;
  84. 	getline(cin,str1); //for blank line
  85. 	rep(i,test_cases) {
  86. 		init();
  87. 		index=0;
  88. 		if(i!=0)
  89. 			cout<<"\n\n";
  90. 		while(getline(cin,str1)) {
  91. 			if(str1=="")
  92. 				break;
  93. 			stringstream converter;
  94. 			converter<<str1;
  95. 			converter>>height;
  96. 			heights[index++]=height;
  97. 		}
  98. 		cout<<"Max hits: ";
  99. 		solve(index);
  100. 	}
  101. 	return 0;
  102. }
  103.  
Success #stdin #stdout 0s 2996KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hihvoU
language:
C++ (gcc 8.3)
created:
11 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!