fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MD (1000000007U)
  5. template<class S, class T> inline S min_L(S a,T b){
  6.   return a<=b?a:b;
  7. }
  8. struct Modint{
  9.   unsigned val;
  10.   Modint(){
  11.     val=0;
  12.   }
  13.   Modint(int a){
  14.     val = ord(a);
  15.   }
  16.   Modint(unsigned a){
  17.     val = ord(a);
  18.   }
  19.   Modint(long long a){
  20.     val = ord(a);
  21.   }
  22.   Modint(unsigned long long a){
  23.     val = ord(a);
  24.   }
  25.   inline unsigned ord(unsigned a){
  26.     return a%MD;
  27.   }
  28.   inline unsigned ord(int a){
  29.     a %= (int)MD;
  30.     if(a < 0){
  31.       a += MD;
  32.     }
  33.     return a;
  34.   }
  35.   inline unsigned ord(unsigned long long a){
  36.     return a%MD;
  37.   }
  38.   inline unsigned ord(long long a){
  39.     a %= (int)MD;
  40.     if(a < 0){
  41.       a += MD;
  42.     }
  43.     return a;
  44.   }
  45.   inline unsigned get(){
  46.     return val;
  47.   }
  48.   inline Modint &operator+=(Modint a){
  49.     val += a.val;
  50.     if(val >= MD){
  51.       val -= MD;
  52.     }
  53.     return *this;
  54.   }
  55.   inline Modint &operator-=(Modint a){
  56.     if(val < a.val){
  57.       val = val + MD - a.val;
  58.     }
  59.     else{
  60.       val -= a.val;
  61.     }
  62.     return *this;
  63.   }
  64.   inline Modint &operator*=(Modint a){
  65.     val = ((unsigned long long)val*a.val)%MD;
  66.     return *this;
  67.   }
  68.   inline Modint &operator/=(Modint a){
  69.     return *this *= a.inverse();
  70.   }
  71.   inline Modint operator+(Modint a){
  72.     return Modint(*this)+=a;
  73.   }
  74.   inline Modint operator-(Modint a){
  75.     return Modint(*this)-=a;
  76.   }
  77.   inline Modint operator*(Modint a){
  78.     return Modint(*this)*=a;
  79.   }
  80.   inline Modint operator/(Modint a){
  81.     return Modint(*this)/=a;
  82.   }
  83.   inline Modint operator+(int a){
  84.     return Modint(*this)+=Modint(a);
  85.   }
  86.   inline Modint operator-(int a){
  87.     return Modint(*this)-=Modint(a);
  88.   }
  89.   inline Modint operator*(int a){
  90.     return Modint(*this)*=Modint(a);
  91.   }
  92.   inline Modint operator/(int a){
  93.     return Modint(*this)/=Modint(a);
  94.   }
  95.   inline Modint operator+(long long a){
  96.     return Modint(*this)+=Modint(a);
  97.   }
  98.   inline Modint operator-(long long a){
  99.     return Modint(*this)-=Modint(a);
  100.   }
  101.   inline Modint operator*(long long a){
  102.     return Modint(*this)*=Modint(a);
  103.   }
  104.   inline Modint operator/(long long a){
  105.     return Modint(*this)/=Modint(a);
  106.   }
  107.   inline Modint operator-(void){
  108.     Modint res;
  109.     if(val){
  110.       res.val=MD-val;
  111.     }
  112.     else{
  113.       res.val=0;
  114.     }
  115.     return res;
  116.   }
  117.   inline operator bool(void){
  118.     return val!=0;
  119.   }
  120.   inline operator int(void){
  121.     return get();
  122.   }
  123.   inline operator long long(void){
  124.     return get();
  125.   }
  126.   inline Modint inverse(){
  127.     int a = val;
  128.     int b = MD;
  129.     int u = 1;
  130.     int v = 0;
  131.     int t;
  132.     Modint res;
  133.     while(b){
  134.       t = a / b;
  135.       a -= t * b;
  136.       swap(a, b);
  137.       u -= t * v;
  138.       swap(u, v);
  139.     }
  140.     if(u < 0){
  141.       u += MD;
  142.     }
  143.     res.val = u;
  144.     return res;
  145.   }
  146.   inline Modint pw(unsigned long long b){
  147.     Modint a(*this);
  148.     Modint res;
  149.     res.val = 1;
  150.     while(b){
  151.       if(b&1){
  152.         res *= a;
  153.       }
  154.       b >>= 1;
  155.       a *= a;
  156.     }
  157.     return res;
  158.   }
  159.   inline bool operator==(int a){
  160.     return ord(a)==val;
  161.   }
  162.   inline bool operator!=(int a){
  163.     return ord(a)!=val;
  164.   }
  165. }
  166. ;
  167. inline Modint operator+(int a, Modint b){
  168.   return Modint(a)+=b;
  169. }
  170. inline Modint operator-(int a, Modint b){
  171.   return Modint(a)-=b;
  172. }
  173. inline Modint operator*(int a, Modint b){
  174.   return Modint(a)*=b;
  175. }
  176. inline Modint operator/(int a, Modint b){
  177.   return Modint(a)/=b;
  178. }
  179. inline Modint operator+(long long a, Modint b){
  180.   return Modint(a)+=b;
  181. }
  182. inline Modint operator-(long long a, Modint b){
  183.   return Modint(a)-=b;
  184. }
  185. inline Modint operator*(long long a, Modint b){
  186.   return Modint(a)*=b;
  187. }
  188. inline Modint operator/(long long a, Modint b){
  189.   return Modint(a)/=b;
  190. }
  191. #define main dummy_main
  192. int main(){
  193.   return 0;
  194. }
  195. #undef main
  196. class Solution{
  197.   public:
  198.   int maxProfit(vector<int>& A, int K){
  199.     int i;
  200.     int N = A.size() + 1;
  201.     Modint res = 0;
  202.     sort(A.rbegin(), A.rend());
  203.     A.push_back(0);
  204.     for(i=(1);i<(N);i++){
  205.       if(K && A[i-1]!=A[i]){
  206.         long long p =min_L(A[i-1] - A[i], K / i);
  207.         res += p * (A[i-1] + A[i-1] - p + 1) / 2 * i;
  208.         K -= p * i;
  209.         A[i-1] -= p;
  210.         if(A[i-1] > A[i] && K){
  211.           res += Modint(A[i-1]) * K;
  212.           K = 0;
  213.         }
  214.       }
  215.     }
  216.     return res;
  217.   }
  218. }
  219. ;
  220. // cLay varsion 20201102-1
  221.  
  222. // --- original code ---
  223. // #define main dummy_main
  224. // {}
  225. // #undef main
  226. // 
  227. // class Solution {
  228. // public:
  229. //   int maxProfit(vector<int>& A, int K) {
  230. //     int N = A.size() + 1;
  231. //     Modint res = 0;
  232. //     sort(A.rbegin(), A.rend());
  233. //     A.push_back(0);
  234. // 
  235. //     rep(i,1,N) if(K && A[i-1]!=A[i]){
  236. //       ll p = min(A[i-1] - A[i], K / i);
  237. //       res += p * (A[i-1] + A[i-1] - p + 1) / 2 * i;
  238. //       K -= p * i;
  239. //       A[i-1] -= p;
  240. //       if(A[i-1] > A[i] && K){
  241. //         res += Modint(A[i-1]) * K;
  242. //         K = 0;
  243. //       }
  244. //     }
  245. //     return res;
  246. //   }
  247. // };
  248.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/yCEBAF
language:
C++ (gcc 8.3)
created:
3 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!