fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <algorithm>
  6. #define FI( type) vector<type>::iterator
  7. #define isBetween( A,B,C) (((A <= B) and (B <= C)))
  8.  
  9. using namespace std;
  10.  
  11. typedef unsigned uint;
  12. typedef vector<int> i_vec ;
  13. typedef vector< vector<int> > iv_vec ;
  14.  
  15. void Begin();
  16.  
  17. struct frend
  18. {
  19.    int food, num, start, end;
  20.    frend( int beg, int last, int f, int n)
  21.    :food( f), num( n), start( beg), end( last) {}
  22.    frend(){}
  23.  
  24.    inline bool operator() (const frend uno, const frend duo)
  25.    {
  26.       return ( uno.food < duo.food ); 
  27.    }
  28. };
  29.  
  30. typedef vector <frend> f_vec;
  31.  
  32. struct Dorm
  33. {
  34.    uint foodNeed, numDays;
  35.    iv_vec action;
  36.    i_vec food_per_day;
  37.    FI( frend) it;
  38.    f_vec Berland;
  39.  
  40. public:   
  41.    Dorm (int n, int f)
  42.    :foodNeed( f), numDays( n)
  43.    {
  44.       food_per_day.resize( n+1 );
  45.  
  46.       for ( uint i=0; i < (uint) n ; ++i )
  47.      scanf( "%d", &food_per_day[i] ), food_per_day[i] -= foodNeed ;//food for Vasya is stored
  48.    }
  49.  
  50.    void Print( int );
  51.    void Solve( );
  52.    void HandleFood( uint&, uint, int&, int & );
  53. };
  54.  
  55.  
  56. int main()
  57. {
  58.    int n, v, m, t(1), k(0);
  59.  
  60.    //Begin();
  61.  
  62.    scanf( "%d%d", &n, &v );
  63.    Dorm	Vasya( n,v );
  64.  
  65.    for ( scanf("%d", &m); m--; )
  66.    {
  67.       scanf( "%d%d%d", &n, &v, &t );
  68.       Vasya.Berland.push_back( frend( n, v, t, ++k ) );
  69.    }
  70.  
  71.    Vasya.Solve();
  72.  
  73.    return 0;
  74. }
  75.  
  76. void Dorm::Solve()
  77. {
  78.    stable_sort( Berland.begin(), Berland.end(), Berland.back() );//sort in order of lowest need for food to highest
  79.    uint Pop(0);
  80.  
  81.    for ( uint p = 0, l(0), prev(0); p < numDays; ++p, l = 0)
  82.    {
  83.       i_vec row;
  84.       l = food_per_day[p], row.push_back(0);
  85.       for ( it = Berland.begin(); it != Berland.end() and (( food_per_day[p] - it->food ) >= 0); ++it )
  86.       {
  87. 	 if ( isBetween(it->start, int(p+1), it->end) )//Are you staying with me this day?
  88. 	 {
  89. 	    food_per_day[p] -= it->food, ++Pop;//increase popularity
  90. 	    ++( row.front() );//number Friends fed
  91. 	    row.push_back( it->num ) ;//index of friend
  92. 	 }
  93.       }
  94.  
  95.       HandleFood(prev, l, food_per_day[p], food_per_day[p+1]);
  96.       action.push_back(row);
  97.    }
  98.  
  99.    Print(Pop);
  100. }
  101.  
  102. void Dorm::Print(int P)
  103. {
  104.    printf( "%d\n", P );
  105.  
  106.    for ( iv_vec::iterator it = action.begin(); it !=action.end(); ++it )
  107.    {
  108.       for ( i_vec::iterator pi = it->begin(); pi != it->end(); ++pi )
  109. 	 printf( "%d ", *pi );
  110.  
  111.       puts( "" );
  112.    }
  113. }
  114.  
  115. void Dorm::HandleFood(uint &left2, uint tot, int &left1 , int &next)
  116. {
  117.    if ( left2 > ( tot -= left1 ) )//did not finish leftover from yesterday?
  118.       left1 -= ( left2 - tot );//Remove the amount not finished
  119.    next += left1;//add whatever is left from today to tomorrow's food
  120.    left2 = left1;//Amount left for today is stored
  121. }
  122.  
  123. void Begin()
  124. {
  125.    freopen("input.txt","r", stdin);
  126.    freopen("output.txt","w", stdout);
  127. }
Success #stdin #stdout 0s 3044KB
comments (?)
stdin
copy 
5 5

233 358 153 273 268

9

1 5 73

4 4 73

1 1 73

1 2 73

5 5 73

1 5 73

4 5 73

3 4 73

5 5 73
stdout
copy 
17
3 1 3 4 
3 1 4 6 
3 1 6 8 
4 1 2 6 7 
4 1 5 6 7
https://ideone.com/LW19fV
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!