BoxerTC

Untitled

Jun 22nd, 2015
397
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sc( x ) scanf( "%d" , &x )
  5. #define REP( i , n ) for( int i = 0 ; i < n ; i++ )
  6. #define clr( t , val ) memset( t , val , sizeof(t) )
  7.  
  8. #define all(v)  v.begin() , v.end()
  9. #define pb push_back
  10. #define SZ( v ) ((int)(v).size())
  11.  
  12. #define mp make_pair
  13. #define fi first
  14. #define se second
  15.  
  16. #define test() cerr << "hola q hace" << endl;
  17. #define DEBUG( x ) cerr <<  #x << "=" << x << endl;
  18. #define DEBUG2( x , y ) cerr << #x << "=" << x << " " << #y << "=" << y << endl;
  19.  
  20. #define N 1000
  21.  
  22. typedef long long ll;
  23. typedef pair< int , int > pii;
  24. typedef vector< pii > vpii;
  25. typedef vector< vpii > vvpii;
  26. typedef vector< vvpii > vvvpii;
  27. typedef vector< int > vi;
  28. typedef vector< vi > vvi;
  29. typedef vector< vvi > vvvi;
  30.  
  31.  
  32. bool used[ N + 5 ][ N + 5 ];
  33. int memo[ N + 5 ][ N + 5 ];
  34. int C[ N + 5 ];
  35. int n , K;
  36. int dx[] = { 1 , -1 };
  37. int dp( int pos , int cur ){
  38.     if( pos == n ) return 0;
  39.     if( used[ pos ][ cur ] ) return memo[ pos ][ cur ];
  40.     used[ pos ][ cur ] = 1;
  41.     int &dev = memo[ pos ][ cur ] = 0;
  42.     REP( k , 2 ){
  43.         int ncur = cur + dx[ k ] * C[ pos ];
  44.         if( ncur >= 0 && ncur <= K )
  45.             dev = max( dev , 1 + dp( pos + 1 , ncur ) );
  46.     }
  47.     return dev;
  48. }
  49. string cad , S = "+-";
  50. void rec( int pos , int cur ){
  51.     if( pos == n ) return;
  52.     int dev = dp( pos , cur );
  53.     REP( k , 2 ){
  54.         int ncur = cur + dx[ k ] * C[ pos ];
  55.         if( ncur >= 0 && ncur <= K )
  56.             if( dev == 1 + dp( pos + 1 , ncur ) ){
  57.                 cad.pb( S[ k ] );
  58.                 rec( pos + 1 , ncur );
  59.                 return;
  60.             }
  61.     }
  62. }
  63. int main(){
  64.     while( sc( n ) == 1 ){
  65.         sc( K );
  66.         REP( i , n ) sc( C[ i ] );
  67.         clr( used , 0 );
  68.         printf( "%d\n" , dp( 0 , 0 ) );
  69.         cad.clear();
  70.         rec( 0 , 0 );
  71.         printf( "%s\n" , cad.c_str() );
  72.     }      
  73. }
Advertisement
Add Comment
Please, Sign In to add comment