fork download
  1. #pragma GCC optimize ("-O3")
  2. #include <bits/stdc++.h>
  3. // #include <ext/pb_ds/assoc_container.hpp>
  4. // #include <ext/pb_ds/tree_policy.hpp>
  5. // using namespace __gnu_pbds;
  6. //#include <boost/multiprecision/cpp_int.hpp>
  7. //using namespace boost::multiprecision;
  8. using namespace std;
  9.  
  10. #define all(c) (c).begin(),(c).end()
  11. #define endl "\n"
  12. #define ff first
  13. #define ss second
  14. #define allr(c) (c).rbegin(),(c).rend()
  15. #define ifr(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  16. #define pof pop_front
  17. #define pob pop_back
  18. #define pb emplace_back
  19. #define pf emplace_front
  20. #define fstm(m,n,r) m.reserve(n);m.max_load_factor(r)
  21. #define mp make_pair
  22. #define mt make_tuple
  23. #define inf LLONG_MAX
  24. #define os tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  25. //order_of_key (k) : Number of items strictly smaller than k .
  26. //find_by_order(k) : K-th element in a set (counting from zero).
  27. const double PI = acos(-1);
  28. typedef complex<double> cd;
  29. typedef long long ll;
  30. ll gcd(){return 0ll;} template<typename T,typename... Args> T gcd(T a,Args... args) { return __gcd(a,(__typeof(a))gcd(args...)); }
  31. typedef map<ll,ll> mll;
  32. typedef map<string,ll> msll;
  33. typedef unordered_map<ll,ll> umap;
  34. typedef vector<ll> vll;
  35. typedef pair<ll,ll> pll;
  36. typedef long double ld;
  37. #define mod 1000000007
  38. #define N 100001
  39.  
  40. int main() {
  41. ios_base::sync_with_stdio(false);
  42. cin.tie(NULL);
  43. cout.tie(NULL);
  44. #ifndef ONLINE_JUDGE
  45. freopen("input.txt","r",stdin);
  46. #endif
  47. // int T;cin>>T;while(T--)
  48. {
  49. ll n, k, t;
  50. cin>>n>>k;
  51. vll pos, neg; ll zero = 0;
  52. ifr(i, 0, n) {
  53. cin>>t;
  54. if(t==0) zero++;
  55. else if(t<0) neg.pb(t);
  56. else pos.pb(t);
  57. }
  58. ll ps = pos.size(), ns = neg.size();
  59. if(k > (ps + ns)) {
  60. cout<<"0\n";
  61. return 0;
  62. }
  63.  
  64. ll ans = 1;
  65. if( k == (ps + ns)) {
  66. // if((ns&1) && zero>0) {
  67. // cout<<"0\n";
  68. // return 0;
  69. // }
  70. ifr(i, 0, ps) ans = (ans*pos[i])%mod;
  71. ifr(i, 0, ns) ans = (ans*neg[i])%mod;
  72. ans = (ans + mod)%mod;
  73. cout<<ans<<endl;
  74. return 0;
  75. }
  76.  
  77. sort(all(pos), greater<ll>());
  78. sort(all(neg));
  79.  
  80. if(ns == 0) {
  81. ans = 1;
  82. ifr(i, 0, k) ans = (ans*pos[i])%mod;
  83. cout<<ans<<endl;
  84. return 0;
  85. }
  86.  
  87.  
  88. if(ps == 0) {
  89. if(k&1) reverse(all(neg));
  90. if((k&1) && zero>0) {
  91. cout<<"0\n";
  92. return 0;
  93. }
  94. ans = 1;
  95. ifr(i, 0, k) ans = (ans*neg[i])%mod;
  96. ans = (ans + mod)%mod;
  97. cout<<ans<<endl;
  98. return 0;
  99. }
  100.  
  101. vector<ld> pre;
  102.  
  103. pre.pb(0);
  104. ifr(i, 0, ps) pre.pb(pre.back() + log(pos[i]));
  105.  
  106. ld lg = 0, sum, msum = 0;
  107. int x=-1, y=-1;
  108.  
  109. for(int i=0; i<=ns; i++) {
  110.  
  111. if(k-i<0 ) break;
  112.  
  113. if(((k-i)>ps) || (i&1)) {
  114. lg += log(-neg[i]);
  115. continue;
  116. }
  117.  
  118. sum = lg + pre[k-i];
  119.  
  120. // cout<<sum<<" "<<msum<<endl;
  121.  
  122. if(msum < sum) {
  123. msum = sum;
  124. x = i; y = k-i;
  125. }
  126.  
  127. if(i!=ns) lg += log(-neg[i]);
  128. }
  129.  
  130. // cout<<x<<" "<<y<<endl;
  131. if(x==-1) {
  132. cout<<0<<endl;
  133. return 0;
  134. }
  135.  
  136. ans = 1;
  137. if((x&1) && zero>0 ) {
  138. cout<<"0\n";
  139. return 0;
  140. }
  141. ifr(i, 0, x) ans = (1ll*ans*neg[i])%mod;
  142. ifr(i, 0, y) ans = (1ll*ans*pos[i])%mod;
  143. ans = (ans + mod)%mod;
  144. cout<<ans<<endl;
  145. }
  146. return 0;
  147. }
  148.  
Success #stdin #stdout 0s 4552KB
stdin
5 4
1 2 3 -1 0
stdout
1000000001