fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct state_t
  6. {
  7.     int cookies, S, T;
  8.  
  9.     state_t( int s ) : cookies( 0 ), S( s ), T( 0 )
  10.     {
  11.     }
  12.  
  13.     int ceil_time_units( int x ) const
  14.     {
  15.         return ( x + S - 1 ) / S;
  16.     }
  17.  
  18.     int min_time( int C )
  19.     {
  20.         return T + ceil_time_units( C - cookies );
  21.     }
  22.  
  23.     int delta( int cost ) const
  24.     {
  25.         int t = 0; if ( cost > cookies ) t = ceil_time_units( cost - cookies ); return t;
  26.     }
  27.  
  28.     void update_time( int delta )
  29.     {
  30.         T += delta, cookies += delta * S;
  31.     }
  32.  
  33.     void buy( int cost, int production )
  34.     {
  35.         cookies -= cost, S += production;
  36.     }
  37. };
  38.  
  39. struct factory_t
  40. {
  41.     int cost, production; bool bought;
  42.  
  43.     factory_t()
  44.     {
  45.         cin >> cost >> production, bought = false;
  46.     }
  47.  
  48.     void buy( state_t &x )
  49.     {
  50.         x.buy(  cost,  production ), bought = true;
  51.     }
  52.  
  53.     void backtrack( state_t &x )
  54.     {
  55.         x.buy( -cost, -production ), bought = false;
  56.     }
  57. };
  58.  
  59. struct factories_t: vector< factory_t >
  60. {
  61.     int C;
  62.  
  63.     int min_time( state_t x )
  64.     {
  65.         int t_min = x.min_time( C );
  66.  
  67.         for( int i = 0, n = size(); i < n; i++ )
  68.             if ( not at( i ).bought )
  69.             {
  70.                 int delta = x.delta( at( i ).cost );
  71.  
  72.                 if ( delta > 0 )
  73.                     x.update_time( delta );
  74.  
  75.                 at( i ).buy( x ), t_min = min( t_min, min_time( x ) ), at( i ).backtrack( x );
  76.  
  77.                 if ( delta > 0 )
  78.                     x.update_time( -delta );
  79.             }
  80.  
  81.         return t_min;
  82.     }
  83. };
  84.  
  85. int main()
  86. {
  87.     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  88.  
  89.     int N, S; factories_t factories; cin >> N >> factories.C >> S, factories.resize( N );
  90.  
  91.     state_t initial_state( S );
  92.  
  93.     cout << factories.min_time( initial_state );
  94. }
  95.  
Success #stdin #stdout 0s 4496KB
comments (?)
stdin
copy 
2 18 1
6 2
5 1
stdout
copy 
12
https://ideone.com/qvbXSS
Cookie Clicker
language:
C++14 (gcc 8.3)
created:
6 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!