fork download
copy 
  1. //
  2. //  main.cpp
  3. //  1136 - Help R2-D2!
  4. //
  5. //  Created by Repon Macbook on 7/5/15.
  6. //  Copyright (c) 2015 Repon Macbook. All rights reserved.
  7. //
  8.  
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11.  
  12. /*------- Constants---- */
  13. #define LMT                     1000006
  14. #define ll                      long long
  15. #define ull                     unsigned long long
  16. #define mod                     1000000007
  17. #define MEMSET_INF              63
  18. #define MEM_VAL                 1061109567
  19. #define FOR(i,n)                for( int i=0 ; i < n ; i++ )
  20. #define mp(i,j)                 make_pair(i,j)
  21. #define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
  22. #define pb(a)                   push_back((a))
  23. #define gc                      getchar_unlocked
  24. #define PI                      acos(-1.0)
  25. #define inf                     1<<30
  26. #define lc                      ((n)<<1)
  27. #define rc                      ((n)<<1 |1)
  28. #define debug(x)                cout <<#x <<" -> " << x << endl;
  29. #define EPS                     1e-9
  30.  
  31. /*---- short Cuts ------- */
  32. #define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
  33. typedef pair<int, int> ii;
  34. typedef vector<int > vi ;
  35. /*------ template functions ------ */
  36. inline void sc(int &x)
  37. {
  38. 	register int c = gc();
  39. 	x = 0;
  40. 	int neg = 0;
  41. 	for(;((c<48 | c>57) && c != '-');c = gc());
  42. 	if(c=='-') {neg=1;c=gc();}
  43. 	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  44. 	if(neg) x=-x;
  45. }
  46.  
  47. template <class T> inline T bigmod(T p,T e,T M){
  48. 	ll ret = 1;
  49. 	for(; e > 0; e >>= 1){
  50. 		if(e & 1) ret = (ret * p) % M;
  51. 		p = (p * p) % M;
  52. 	} return (T)ret;
  53. }
  54. template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
  55. template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
  56.  
  57. /*************************** END OF TEMPLATE ****************************/
  58.  
  59. int iAr[LMT];
  60. int block;
  61. int DP[5 * LMT];
  62. char s[100];
  63.  
  64. void upd( int n , int b , int e ,int val ){
  65.       if( b == e ) {
  66.             iAr[b] -= val;
  67.             DP[n] -= val;
  68.             return;
  69.       }
  70.       int mid = (b+e)/2;
  71.       if(DP[lc] >= val ) {
  72.             upd(lc, b, mid, val);
  73.       }
  74.       else upd(rc, mid+1, e, val);
  75.       DP[n] = max(DP[lc] , DP[rc]);
  76. }
  77. int main()
  78. {
  79.       int cap , boxes , tc = 0 ;
  80. 	while(scanf("%d" ,& cap) == 1) {
  81.  
  82.             scanf("%d" , &boxes );
  83.             for(int i = 0; i < boxes ; i ++ ) iAr[i] = cap;
  84.             block = sqrt(LMT ) + 1;
  85.  
  86.             for(int i = 0; i < 3 * boxes + 5 ; i ++ ) DP[i] = cap;
  87.  
  88.             for( int i = 0 ; i < boxes ; i ++ ) {
  89.                   scanf("%s" , s);
  90.                   if(s[0] == 'b' ) {
  91.                         int lo , u ;
  92.                         scanf("%d %d",&lo,&u );
  93.  
  94.                         for( int j = 0 ; i < boxes && j < lo ; i ++ , j ++ ) {
  95.                               upd(1, 0, boxes - 1, u);
  96.                         }
  97.                         i --;
  98.                   }
  99.                   else {
  100.                         int sum = 0;
  101.                         for(int i = 0; s[i] ; i ++ ) {
  102.                               sum = 10  * sum + s[i] -'0';
  103.                         }
  104.                         upd(1, 0, boxes - 1, sum);
  105.  
  106.                   }
  107.             }
  108.             ll ans = 0 ,cnt = 0 ;
  109.             for( int i = 0; i < boxes ; i ++ ) {
  110.                   if(iAr[i] == cap ) break;
  111.                   else {
  112.                         cnt++ ;
  113.                         ans += iAr[i];
  114.                   }
  115.             }
  116.             if( tc) printf("\n");
  117.             printf("%lld %lld\n" , cnt , ans);
  118.             tc = 1;
  119.       }
  120.  
  121. 	return 0;
  122. }
  123.  
Success #stdin #stdout 0s 26536KB
comments (?)
stdin
copy 
100
3
50
25
70

100
4
50
b 2 40
20
stdout
copy 
2 55

2 50
https://ideone.com/srPTth
language:
C++14 (gcc 8.3)
created:
8 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!