fork download
copy 
  1. /*
  2.   Name:
  3.   Copyright: DHKHTN - DHQGHN
  4.   Author: Nguyen Dinh Nhat
  5.   Date: 26/07/10 21:40
  6.   Description: 
  7. 		SPSEQ
  8. 		https://v...content-available-to-author-only...j.pl/problems/SPSEQ/
  9. */
  10.  
  11.  
  12. #include <stdio.h>
  13. #include <iostream>
  14. #include <stdlib.h>
  15. #include <string.h>
  16. #include <algorithm>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define TI freopen("test.inp","rt",stdin)
  21.  
  22. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  23. #define FORD(i,a,b) for(int i=a;i>=b;i--)
  24. #define REP(i,n) for(int i=0;i<n;i++)
  25.  
  26. #define MAX 100005
  27.  
  28. int F[3][MAX],A[MAX],start_of[MAX];
  29. int m_t=0,m_g=0,N;
  30.  
  31.  
  32. void decode (){
  33. 	scanf ("%d\n",&N);
  34. 	FOR (i,1,N)
  35. 		scanf ("%d",&A[i]);
  36. }
  37.  
  38. int tim_t (int i){
  39. 	int truoc=0,sau=m_t+1,hientai;
  40. 	do {
  41. 		hientai=(truoc+sau)/2;
  42. 		if (A[start_of[hientai]]<A[i]) truoc=hientai;
  43. 		else sau=hientai;
  44.  
  45. 	}while (sau!=truoc+1);
  46. 	return truoc;
  47. }
  48.  
  49. // luu chi so vao trong th giam
  50. int tim_g (int i){
  51. 	int truoc=0,sau=m_g+1,hientai,j;
  52. 	while (sau!=truoc+1){
  53. 		hientai=(truoc+sau)/2;
  54. 		if (A[start_of[hientai]]>A[i]) truoc=hientai;
  55. 		else sau=hientai;
  56. 	}
  57. 	return truoc;
  58. }
  59.  
  60. void SPSEQ (){
  61. 	int Max=0,j,rs=0;
  62. 	// xet truong hop tang
  63. 	FOR (i,1,N){
  64. 		j=tim_t (i)+1;
  65. 		F[0][i]=j;
  66. 		if (j>m_t){
  67. 			m_t=j;
  68. 			start_of[j]=i;
  69. 		}
  70. 		else if (A[i]<A[start_of[j]]){
  71. 			start_of[j]=i;
  72. 		}
  73. 	}
  74. 	FOR (i,1,N) start_of[i]=0;
  75. 	// xet truong hop giam
  76. 	FOR (i,1,N){
  77. 		j=tim_g (i)+1;
  78. 		F[1][i]=j-1;
  79. 		if (j>m_g){
  80. 			m_g=j;
  81. 			start_of [j]=i;
  82. 		}
  83. 		else if (A[i]>A[start_of[j]])
  84. 			start_of [j]=i;
  85. 		// tim Max là chi so lon nhat 
  86. 		if (A[i]>=A[Max]) Max=i;
  87. 		F[2][i]=max(F[0][i],F[1][i]+F[0][Max]);
  88. 		rs=max(rs,F[2][i]);	
  89. 	}
  90.  
  91. 	cout<<rs<<endl;
  92. }
  93.  
  94.  
  95. //#include <conio.h>
  96. int main ()
  97. {
  98. //	TI;
  99. 	decode ();
  100. 	SPSEQ ();
  101. //	getch ();
  102.     return 0;
  103. }
  104.  
stdin
copy 
1000
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  171  172  173  174  175  176  177  178  179  180  181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  196  197  198  199  200  201  202  203  204  205  206  207  208  209  210  211  212  213  214  215  216  217  218  219  220  221  222  223  224  225  226  227  228  229  230  231  232  233  234  235  236  237  238  239  240  241  242  243  244  245  246  247  248  249  250  251  252  253  254  255  256  257  258  259  260  261  262  263  264  265  266  267  268  269  270  271  272  273  274  275  276  277  278  279  280  281  282  283  284  285  286  287  288  289  290  291  292  293  294  295  296  297  298  299  300  301  302  303  304  305  306  307  308  309  310  311  312  313  314  315  316  317  318  319  320  321  322  323  324  325  326  327  328  329  330  331  332  333  334  335  336  337  338  339  340  341  342  343  344  345  346  347  348  349  350  351  352  353  354  355  356  357  358  359  360  361  362  363  364  365  366  367  368  369  370  371  372  373  374  375  376  377  378  379  380  381  382  383  384  385  386  387  388  389  390  391  392  393  394  395  396  397  398  399  400  401  402  403  404  405  406  407  408  409  410  411  412  413  414  415  416  417  418  419  420  421  422  423  424  425  426  427  428  429  430  431  432  433  434  435  436  437  438  439  440  441  442  443  444  445  446  447  448  449  450  451  452  453  454  455  456  457  458  459  460  461  462  463  464  465  466  467  468  469  470  471  472  473  474  475  476  477  478  479  480  481  482  483  484  485  486  487  488  489  490  491  492  493  494  495  496  497  498  499  500  501  502  503  504  505  506  507  508  509  510  511  512  513  514  515  516  517  518  519  520  521  522  523  524  525  526  527  528  529  530  531  532  533  534  535  536  537  538  539  540  541  542  543  544  545  546  547  548  549  550  551  552  553  554  555  556  557  558  559  560  561  562  563  564  565  566  567  568  569  570  571  572  573  574  575  576  577  578  579  580  581  582  583  584  585  586  587  588  589  590  591  592  593  594  595  596  597  598  599  600  601  602  603  604  605  606  607  608  609  610  611  612  613  614  615  616  617  618  619  620  621  622  623  624  625  626  627  628  629  630  631  632  633  634  635  636  637  638  639  640  641  642  643  644  645  646  647  648  649  650  651  652  653  654  655  656  657  658  659  660  661  662  663  664  665  666  667  668  669  670  671  672  673  674  675  676  677  678  679  680  681  682  683  684  685  686  687  688  689  690  691  692  693  694  695  696  697  698  699  700  701  702  703  704  705  706  707  708  709  710  711  712  713  714  715  716  717  718  719  720  721  722  723  724  725  726  727  728  729  730  731  732  733  734  735  736  737  738  739  740  741  742  743  744  745  746  747  748  749  750  751  752  753  754  755  756  757  758  759  760  761  762  763  764  765  766  767  768  769  770  771  772  773  774  775  776  777  778  779  780  781  782  783  784  785  786  787  788  789  790  791  792  793  794  795  796  797  798  799  800  801  802  803  804  805  806  807  808  809  810  811  812  813  814  815  816  817  818  819  820  821  822  823  824  825  826  827  828  829  830  831  832  833  834  835  836  837  838  839  840  841  842  843  844  845  846  847  848  849  850  851  852  853  854  855  856  857  858  859  860  861  862  863  864  865  866  867  868  869  870  871  872  873  874  875  876  877  878  879  880  881  882  883  884  885  886  887  888  889  890  891  892  893  894  895  896  897  898  899  900  901  902  903  904  905  906  907  908  909  910  911  912  913  914  915  916  917  918  919  920  921  922  923  924  925  926  927  928  929  930  931  932  933  934  935  936  937  938  939  940  941  942  943  944  945  946  947  948  949  950  951  952  953  954  955  956  957  958  959  960  961  962  963  964  965  966  967  968  969  970  971  972  973  974  975  976  977  978  979  980  981  982  983  984  985  986  987  988  989  990  991  992  993  994  995  996  997  998  999  1000
compilation info 
prog.cpp: In function ‘void decode()’:
prog.cpp:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp: In function ‘int tim_g(int)’:
prog.cpp:51: warning: unused variable ‘j’
stdout
copy 
1000
https://ideone.com/fdyYA
language:
C++ (gcc 8.3)
created:
15 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!