const int OO = ( int ) ( 1e9 + 7 ) ;
const int MAXN = ( int ) ( 1e3 + 5 ) ;
struct Cashier
{
long long m;
long long s, p;
} ;
Cashier a[ MAXN] ;
bool used[ MAXN] ;
int r, b, c;
bool check( long long t)
{
memset ( used, false , sizeof ( used) ) ;
int num = b;
for ( int i = 1 ; i <= r; ++ i)
{
if ( num <= 0 )
break ;
int pos = 0 ;
int maxItems = 0 ;
for ( int j = 1 ; j <= c; ++ j)
if ( ! used[ j] )
{
int items = min( a[ j] .m , ( t - a[ j] .p ) / a[ j] .s ) ;
if ( items > maxItems)
pos = j, maxItems = items;
}
num - = maxItems;
used[ pos] = true ;
}
return num <= 0 ;
}
void Inp( )
{
int t;
cin >> t;
For( iTest, 1 , t)
{
cout << "Case #" << iTest << ": " ;
cin >> r >> b >> c;
for ( int i = 1 ; i <= c; ++ i)
cin >> a[ i] .m >> a[ i] .s >> a[ i] .p ;
long long lo = 0 , hi = 1LL * OO * OO + OO, mid = ( lo + hi) / 2 ;
while ( lo ! = mid && hi ! = mid)
{
if ( check( mid) )
hi = mid;
else
lo = mid;
mid = ( lo + hi) / 2 ;
}
for ( long long i = lo; i <= hi; ++ i)
if ( check( i) )
{
cout << i;
break ;
}
cout << '\n ' ;
}
}
Y29uc3QgaW50IE9PID0gKGludCkoMWU5ICsgNyk7CmNvbnN0IGludCBNQVhOID0gKGludCkoMWUzKzUpOwoKc3RydWN0IENhc2hpZXIKewogICAgbG9uZyBsb25nIG07CiAgICBsb25nIGxvbmcgcywgcDsKfTsKCkNhc2hpZXIgYVtNQVhOXTsKYm9vbCB1c2VkW01BWE5dOwppbnQgciwgYiwgYzsKCmJvb2wgY2hlY2sobG9uZyBsb25nIHQpCnsKICAgIG1lbXNldCh1c2VkLCBmYWxzZSwgc2l6ZW9mKHVzZWQpKTsKICAgIGludCBudW0gPSBiOwogICAgZm9yKGludCBpID0gMTsgaSA8PSByOyArK2kpCiAgICB7CiAgICAgICAgaWYgKG51bSA8PSAwKQogICAgICAgICAgICBicmVhazsKICAgICAgICBpbnQgcG9zID0gMDsKICAgICAgICBpbnQgbWF4SXRlbXMgPSAwOwogICAgICAgIGZvcihpbnQgaiA9IDE7IGogPD0gYzsgKytqKQogICAgICAgICAgICBpZiAoIXVzZWRbal0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBpdGVtcyA9IG1pbihhW2pdLm0sICh0IC0gYVtqXS5wKSAvIGFbal0ucyk7CiAgICAgICAgICAgICAgICBpZiAoaXRlbXMgPiBtYXhJdGVtcykKICAgICAgICAgICAgICAgICAgICBwb3MgPSBqLCBtYXhJdGVtcyA9IGl0ZW1zOwogICAgICAgICAgICB9CiAgICAgICAgbnVtIC09IG1heEl0ZW1zOwogICAgICAgIHVzZWRbcG9zXSA9IHRydWU7CiAgICB9CiAgICByZXR1cm4gbnVtIDw9IDA7Cn0KCnZvaWQgSW5wKCkKewogICAgaW50IHQ7CiAgICBjaW4gPj4gdDsKICAgIEZvcihpVGVzdCwgMSwgdCkKICAgIHsKICAgICAgICBjb3V0IDw8ICJDYXNlICMiIDw8IGlUZXN0IDw8ICI6ICI7CiAgICAgICAgY2luID4+IHIgPj4gYiA+PiBjOwogICAgICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gYzsgKytpKQogICAgICAgICAgICBjaW4gPj4gYVtpXS5tID4+IGFbaV0ucyA+PiBhW2ldLnA7CiAgICAgICAgbG9uZyBsb25nIGxvID0gMCwgaGkgPSAxTEwgKiBPTyAqIE9PICsgT08sIG1pZCA9IChsbyArIGhpKSAvIDI7CiAgICAgICAgd2hpbGUgKGxvICE9IG1pZCAmJiBoaSAhPSBtaWQpCiAgICAgICAgewogICAgICAgICAgICBpZiAoY2hlY2sobWlkKSkKICAgICAgICAgICAgICAgIGhpID0gbWlkOwogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICBsbyA9IG1pZDsKICAgICAgICAgICAgbWlkID0gKGxvICsgaGkpIC8gMjsKICAgICAgICB9CiAgICAgICAgZm9yKGxvbmcgbG9uZyBpID0gbG87IGkgPD0gaGk7ICsraSkKICAgICAgICAgICAgaWYgKGNoZWNrKGkpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjb3V0IDw8IGk7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgIGNvdXQgPDwgJ1xuJzsKICAgIH0KfQ==
compilation info
prog.cpp: In function ‘bool check(long long int)’:
prog.cpp:16:37: error: ‘memset’ was not declared in this scope
memset(used, false, sizeof(used));
^
prog.cpp:27:62: error: ‘min’ was not declared in this scope
int items = min(a[j].m, (t - a[j].p) / a[j].s);
^
prog.cpp: In function ‘void Inp()’:
prog.cpp:40:5: error: ‘cin’ was not declared in this scope
cin >> t;
^~~
prog.cpp:41:9: error: ‘iTest’ was not declared in this scope
For(iTest, 1, t)
^~~~~
prog.cpp:41:20: error: ‘For’ was not declared in this scope
For(iTest, 1, t)
^
stdout