fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. template<class T> struct cLtraits_identity{
  7.   using type = T;
  8. }
  9. ;
  10. template<class T> using cLtraits_try_make_signed =
  11.   typename conditional<
  12.     is_integral<T>::value,
  13.     make_signed<T>,
  14.     cLtraits_identity<T>
  15.     >::type;
  16. template <class S, class T> struct cLtraits_common_type{
  17.   using tS = typename cLtraits_try_make_signed<S>::type;
  18.   using tT = typename cLtraits_try_make_signed<T>::type;
  19.   using type = typename common_type<tS,tT>::type;
  20. }
  21. ;
  22. template<class S, class T> inline auto max_L(S a, T b)
  23. -> typename cLtraits_common_type<S,T>::type{
  24.   return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
  25. }
  26. template<class T1, class T2, class T3> inline T1 Kth1_L(const T1 a, const T2 b, const T3 c){
  27.   if(a <= b){
  28.     if(b <= c){
  29.       return b;
  30.     }
  31.     if(c <= a){
  32.       return a;
  33.     }
  34.     return c;
  35.   }
  36.   if(a <= c){
  37.     return a;
  38.   }
  39.   if(c <= b){
  40.     return b;
  41.   }
  42.   return c;
  43. }
  44. inline int my_getchar_unlocked(){
  45.   static char buf[1048576];
  46.   static int s = 1048576;
  47.   static int e = 1048576;
  48.   if(s == e && e == 1048576){
  49.     e = fread_unlocked(buf, 1, 1048576, stdin);
  50.     s = 0;
  51.   }
  52.   if(s == e){
  53.     return EOF;
  54.   }
  55.   return buf[s++];
  56. }
  57. inline void rd(int &x){
  58.   int k;
  59.   int m=0;
  60.   x=0;
  61.   for(;;){
  62.     k = my_getchar_unlocked();
  63.     if(k=='-'){
  64.       m=1;
  65.       break;
  66.     }
  67.     if('0'<=k&&k<='9'){
  68.       x=k-'0';
  69.       break;
  70.     }
  71.   }
  72.   for(;;){
  73.     k = my_getchar_unlocked();
  74.     if(k<'0'||k>'9'){
  75.       break;
  76.     }
  77.     x=x*10+k-'0';
  78.   }
  79.   if(m){
  80.     x=-x;
  81.   }
  82. }
  83. inline void rd(long long &x){
  84.   int k;
  85.   int m=0;
  86.   x=0;
  87.   for(;;){
  88.     k = my_getchar_unlocked();
  89.     if(k=='-'){
  90.       m=1;
  91.       break;
  92.     }
  93.     if('0'<=k&&k<='9'){
  94.       x=k-'0';
  95.       break;
  96.     }
  97.   }
  98.   for(;;){
  99.     k = my_getchar_unlocked();
  100.     if(k<'0'||k>'9'){
  101.       break;
  102.     }
  103.     x=x*10+k-'0';
  104.   }
  105.   if(m){
  106.     x=-x;
  107.   }
  108. }
  109. inline int rd_int(void){
  110.   int x;
  111.   rd(x);
  112.   return x;
  113. }
  114. struct MY_WRITER{
  115.   char buf[1048576];
  116.   int s;
  117.   int e;
  118.   MY_WRITER(){
  119.     s = 0;
  120.     e = 1048576;
  121.   }
  122.   ~MY_WRITER(){
  123.     if(s){
  124.       fwrite_unlocked(buf, 1, s, stdout);
  125.     }
  126.   }
  127. }
  128. ;
  129. MY_WRITER MY_WRITER_VAR;
  130. void my_putchar_unlocked(int a){
  131.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  132.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  133.     MY_WRITER_VAR.s = 0;
  134.   }
  135.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  136. }
  137. inline void wt_L(char a){
  138.   my_putchar_unlocked(a);
  139. }
  140. inline void wt_L(long long x){
  141.   int s=0;
  142.   int m=0;
  143.   char f[20];
  144.   if(x<0){
  145.     m=1;
  146.     x=-x;
  147.   }
  148.   while(x){
  149.     f[s++]=x%10;
  150.     x/=10;
  151.   }
  152.   if(!s){
  153.     f[s++]=0;
  154.   }
  155.   if(m){
  156.     my_putchar_unlocked('-');
  157.   }
  158.   while(s--){
  159.     my_putchar_unlocked(f[s]+'0');
  160.   }
  161. }
  162. template<class S, class T> inline S divup_L(S a, T b){
  163.   return (a+b-1)/b;
  164. }
  165. template<class S, class T> inline S chmax(S &a, T b){
  166.   if(a<b){
  167.     a=b;
  168.   }
  169.   return a;
  170. }
  171. long long CP;
  172. long long CM;
  173. int H0;
  174. int A1;
  175. int D1;
  176. int N;
  177. int getm(int D){
  178.   return (divup_L(H0,max_L(1, A1 - D)));
  179. }
  180. long long getd(int P0, int K0, int m){
  181.   if(K0 >= m){
  182.     return CM * P0 * m;
  183.   }
  184.   return CM * P0 * K0 + CP * (m-K0);
  185. }
  186. int main(){
  187.   int KL2GvlyY;
  188.   int Q5VJL1cS = rd_int();
  189.   for(KL2GvlyY=(0);KL2GvlyY<(Q5VJL1cS);KL2GvlyY++){
  190.     rd(CP);
  191.     rd(CM);
  192.     rd(H0);
  193.     rd(A1);
  194.     rd(D1);
  195.     rd(N);
  196.     H0 =(divup_L(H0,CP));
  197.     int D = 0;
  198.     int P0;
  199.     int K0;
  200.     int m;
  201.     int n;
  202.     long long res = 0;
  203.     while(D <= N && D < A1){
  204.       n = N - D;
  205.       m = getm(D);
  206.       chmax(res, m * CP *max_L(1, n - D1));
  207.       K0 =Kth1_L(0, (CM * n - CP) / (2 * CM), m);
  208.       P0 = n - K0;
  209.       chmax(res, getd(P0,K0,m));
  210.       if(P0){
  211.         chmax(res, getd(P0-1,K0+1,m));
  212.       }
  213.       D = A1 - ((divup_L(H0,m))) + 1;
  214.     }
  215.     wt_L(res);
  216.     wt_L('\n');
  217.   }
  218.   return 0;
  219. }
  220. // cLay version 20210926-1
  221.  
  222. // --- original code ---
  223. // ll CP, CM; int H0, A1, D1, N;
  224. // 
  225. // int getm(int D){
  226. //   return H0 /+ max(1, A1 - D);
  227. // }
  228. // 
  229. // ll getd(int P0, int K0, int m){
  230. //   if(K0 >= m) return CM * P0 * m;
  231. //   return CM * P0 * K0 + CP * (m-K0);
  232. // }
  233. // 
  234. // {
  235. //   REP(rd_int()){
  236. //     rd(CP, CM, H0, A1, D1, N);
  237. //     H0 = H0 /+ CP;
  238. // 
  239. //     int D = 0, P0, K0, m, n;
  240. //     ll res = 0;
  241. // 
  242. //     while(D <= N && D < A1){
  243. //       n = N - D;
  244. //       m = getm(D);
  245. // 
  246. //       res >?= m * CP * max(1, n - D1);
  247. // 
  248. //       K0 = Kth1(0, (CM * n - CP) / (2 * CM), m);
  249. //       P0 = n - K0;
  250. //       res >?= getd(P0,K0,m);
  251. //       if(P0) res >?= getd(P0-1,K0+1,m);
  252. // 
  253. //       D = A1 - (H0 /+ m) + 1;
  254. //     }
  255. //     wt(res);
  256. //   }
  257. // }
  258.  
Time limit exceeded #stdin #stdout 5s 5444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pBbfXM
language:
C++ (gcc 8.3)
created:
2 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!