fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace std;
  5. #define PB push_back
  6. #define MP make_pair
  7. #define LL long long
  8. #define int LL
  9. #define FOR(i,a,b) for(int i = (a); i <= (b); i++)
  10. #define RE(i,n) FOR(i,1,n)
  11. #define REP(i,n) FOR(i,0,(int)(n)-1)
  12. #define R(i,n) REP(i,n)
  13. #define VI vector<int>
  14. #define PII pair<int,int>
  15. #define LD long double
  16. #define FI first
  17. #define SE second
  18. #define st FI
  19. #define nd SE
  20. #define ALL(x) (x).begin(), (x).end()
  21. #define SZ(x) ((int)(x).size())
  22.  
  23. #define unordered_map __fast_unordered_map
  24. template<class Key, class Value, class Hash = std::hash<Key>>
  25. using unordered_map = __gnu_pbds::gp_hash_table<Key, Value, Hash>;
  26.  
  27. template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
  28. template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }
  29.  
  30. template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
  31. template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  32.   while(*sdbg!=',')cerr<<*sdbg++;
  33.   cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
  34. }
  35.  
  36. template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  37.   os << "["; for (auto vv : V) os << vv << ","; return os << "]";
  38. }
  39. template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  40.   return os << "(" << P.st << "," << P.nd << ")";
  41. }
  42.  
  43. #ifdef LOCAL
  44. #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
  45. #else
  46. #define debug(...) (__VA_ARGS__)
  47. #define cerr if(0)cout
  48. #endif
  49.  
  50. int have_testcases_from, have_testcases_to;
  51.  
  52. const LD kPi = 2 * acos(0);
  53.  
  54. struct CD {
  55.   LD re, im;
  56.   CD operator=(LD a) { re = a; im = 0; return *this; }
  57.   CD operator*(CD& z) { return {re * z.re - im * z.im, re * z.im + im * z.re}; }
  58.   void operator*=(CD& z) { *this = (*this * z); }
  59.   CD operator+(CD& z) { return {re + z.re, im + z.im}; }
  60.   CD operator-(CD& z) { return {re - z.re, im - z.im}; }
  61.   void operator/=(LD f) { re /= f; im /= f; }
  62. };
  63.  
  64. int powMod(int a, int n, int p) {
  65.   int res = 1;
  66.   while (n) {
  67.     if (n & 1) { res = ((LL)res * a) % p; }
  68.     n >>= 1; a = ((LL)a * a) % p;
  69.   }
  70.   return res;
  71. }
  72.  
  73. struct FFT {
  74. private:
  75.   CD *A, *B, *tmp, *res, *omega;
  76.   int *perm;
  77.   int maxh;
  78.   // not needed if this is going to be used just once
  79.   void Clear(int n) {
  80.     REP (i, n) { A[i] = B[i] = res[i] = tmp[i] = 0; }
  81.   }
  82.  
  83.   void fft(CD* from, CD* to, int depth, bool inv){
  84.     int N = (1 << depth);
  85.     for (int i = 0; i < N; i++) { to[perm[i] >> (maxh - depth)] = from[i]; }
  86.     RE (m, depth) {
  87.       int step = 1 << m;
  88.       for (int pos = 0; pos < N; pos += step){
  89.         int cur = 0;
  90.         int delta = 1 << (maxh - m);
  91.         if (!inv) { cur = 1 << maxh; delta *= -1; }
  92.         CD *lft = to + pos, *rgt = lft + step / 2;
  93.         REP (k, step / 2) {
  94.           CD a = *lft, b = omega[cur] * *rgt;
  95.           *lft++ = a + b; *rgt++ = a - b;
  96.           cur += delta;
  97.         }
  98.       }
  99.     }
  100.  
  101.     if (inv) { REP (i, N) { to[i] /= N; } }
  102.   }
  103.  
  104. public:
  105.   FFT(int deg) {
  106.     maxh = 0; int N = 1, h = -1;
  107.     while (N <= 2 * deg) { maxh++; N *= 2; }
  108.     deg = N + 20;
  109.     A = new CD[deg];
  110.     B = new CD[deg];
  111.     res = new CD[deg];
  112.     tmp = new CD[deg];
  113.     omega = new CD[deg];
  114.     perm = new int[deg];
  115.     LD ang = 2 * kPi / N;
  116.     REP (i, N + 1) { omega[i] = {cos(i * ang), sin(i * ang)}; }
  117.     perm[0] = 0;
  118.     RE (i, N - 1) {
  119.       if ((i & (i - 1)) == 0) { h++; }
  120.       perm[i] = perm[i ^ (1 << h)] | (1 << (maxh - h - 1));
  121.     }
  122.   }
  123.   VI mul_less_exact(VI Q, VI R) {
  124.     int depth = 0, size = 1;
  125.     int N = SZ(Q) + SZ(R) - 1;
  126.     while (size < N) { depth++; size *= 2; }
  127.     Clear(size);
  128.     copy(ALL(Q), A); copy(ALL(R), B);
  129.     fft(A, res, depth, false);
  130.     fft(B, tmp, depth, false);
  131.     REP (i, size) tmp[i] *= res[i];
  132.     fft(tmp, res, depth, true);
  133.     VI ans;
  134.     REP (i, N) { ans.PB((long long)round(res[i].re)); }
  135.     return ans;
  136.   }
  137.  
  138.   VI Prepare(VI& v, int base, int bpow) {
  139.     VI ans;
  140.     for (int x : v) { ans.PB(bpow ? x / base : x % base); }
  141.     return ans;
  142.   }
  143.   int Sum(VI& v, int P) { // debug/assert purposes only
  144.     return accumulate(ALL(v), 0LL) % P;
  145.   }
  146.   VI mul_exact(VI Q, VI R) {
  147.     int base = 32000;
  148.     LL pows[] = {1, base, (int)1LL * base * base};
  149.     VI ans(SZ(Q) + SZ(R) - 1);
  150.     REP (q, 2) {
  151.       VI W = Prepare(Q, base, q);
  152.       REP (r, 2) {
  153.         VI V = Prepare(R, base, r);
  154.         VI C = mul_less_exact(W, V);
  155.         REP (i, SZ(C)) { ans[i] = (ans[i] + 1LL * C[i] * pows[q + r]); }
  156.       }
  157.     }
  158.     return ans;
  159.   }
  160. };
  161.  
  162. FFT global_fft(30 * 1000 + 50);
  163. const LL Infty = 4e18;
  164.  
  165. struct Testcase {
  166.   int tidx_;
  167.  
  168.   Testcase(int idx) : tidx_(idx) {}
  169.  
  170.   int N;
  171.   vector<LL> vals_minus, vals_plus;
  172.  
  173.   void Input() {
  174.     cin >> N;
  175.     for (int i = 0; i < N; ++i) {
  176.       int h;
  177.       cin >> h;
  178.       if (h > 0)
  179.         vals_plus.push_back(h);
  180.       else
  181.         vals_minus.push_back(h);
  182.     }
  183.   }
  184.  
  185.   vector<LL> SolvePlusForSuffixes(vector<LL> plus) {
  186.     sort(ALL(plus));
  187.     debug(plus);
  188.  
  189.     const vector<int> mul_with_first =
  190.       global_fft.mul_exact(plus, plus);
  191.  
  192.     debug(mul_with_first);
  193.  
  194.     vector<LL> answer(SZ(plus) + 1);
  195.  
  196.     for (int len = 2; len <= SZ(plus); ++len) {
  197.       answer[len] = answer[len - 1] + plus[0] * plus[len - 1];
  198.       if (len % 2 == 0)
  199.         mini(answer[len], mul_with_first[len - 1] / 2);
  200.     }
  201.  
  202.     answer[1] = Infty;
  203.     return answer;
  204.   }
  205.  
  206.   LL SolvePlusOnly() {
  207.     return SolvePlusForSuffixes(vals_plus)[SZ(vals_plus)];
  208.   }
  209.  
  210.   LL SolvePlusMinus() {
  211.     sort(ALL(vals_plus));
  212.     sort(ALL(vals_minus));
  213.  
  214.     debug(vals_plus, vals_minus);
  215.  
  216.     LL answer = Infty;
  217.     const vector<LL> minus_without_first =
  218.       vector<int>(vals_minus.begin() + 1, vals_minus.end());
  219.  
  220.     vector<LL> convs_plus_minus =
  221.       global_fft.mul_exact(minus_without_first, vals_plus);
  222.     convs_plus_minus.insert(convs_plus_minus.begin(), 0LL);
  223.  
  224.     debug(convs_plus_minus);
  225.  
  226.     int M = SZ(vals_minus);
  227.     int P = SZ(vals_plus);
  228.     vector<LL> best_for_suffix(M + 1, Infty);
  229.     if (M >= P) {
  230.       best_for_suffix[P] = 0;
  231.       for (int i = 0; i < P; ++i)
  232.         best_for_suffix[P] += vals_plus[i] * vals_minus[P - i - 1];
  233.     }
  234.  
  235.  
  236.     {
  237.       LL increase = 0;
  238.       for (int num_small = 1; num_small <= P; ++num_small) {
  239.         if (num_small >= 1)
  240.           increase += vals_minus[0] * vals_plus[P - num_small];
  241.         const int num_paired = P - num_small;
  242.         if (num_paired + 1 > M) { continue; }
  243.         debug(num_small, num_paired, best_for_suffix);
  244.         mini(best_for_suffix[num_paired + 1],
  245.              convs_plus_minus[num_paired] + increase);
  246.         debug(num_small, num_paired, best_for_suffix);
  247.       }
  248.     }
  249.  
  250.     vector<LL> minus_revved(ALL(vals_minus));
  251.     for (int &x : minus_revved) { x = -x; }
  252.     vector<LL> best_for_prefix = SolvePlusForSuffixes(minus_revved);
  253.  
  254.     debug(best_for_prefix, best_for_suffix);
  255.  
  256.     for (int len_prefix = 0; len_prefix <= M; ++len_prefix)
  257.       mini(answer, best_for_prefix[len_prefix] + best_for_suffix[M - len_prefix]);
  258.  
  259.     if (M >= 2)
  260.       mini(answer, best_for_prefix[2] + best_for_suffix[M - 1]);
  261.  
  262.     return answer;
  263.   }
  264.  
  265.   void Run() {
  266.     Input();
  267.     LL result = 0;
  268.     if (tidx_ < have_testcases_from || tidx_ > have_testcases_to) { return; }
  269.  
  270.     if (vals_minus.empty()) {
  271.       result = SolvePlusOnly();
  272.     } else if (vals_plus.empty()) {
  273.       for (int x : vals_minus)
  274.         vals_plus.push_back(-x);
  275.       vals_minus.clear();
  276.       result = SolvePlusOnly();
  277.     } else {
  278.       result = SolvePlusMinus();
  279.     }
  280.  
  281.     cout << "Case #" << tidx_ << ": " << result << "\n";
  282.   }
  283. };
  284.  
  285. int32_t main(int32_t argc, char **argv) {
  286.   ios_base::sync_with_stdio(0);
  287.   cin.tie(0);
  288.   cout << fixed << setprecision(11);
  289.   cerr << fixed << setprecision(6);
  290.  
  291.   int T;
  292.   cin >> T;
  293.  
  294.   if (argc > 1) {
  295.     assert(argc == 3);
  296.     const int thread_idx = atoi(argv[1]);
  297.     const int thread_num = atoi(argv[2]);
  298.     assert(0 <= thread_idx && thread_idx < thread_num);
  299.     have_testcases_from = (thread_idx * T) / thread_num + 1;
  300.     have_testcases_to = ((thread_idx + 1) * T) / thread_num;
  301.   } else {
  302.     have_testcases_from = 1;
  303.     have_testcases_to = T;
  304.   }
  305.  
  306.   for (int i = 1; i <= T; ++i)
  307.     Testcase(i).Run();
  308. }
Success #stdin #stdout 0.02s 5976KB
comments (?)
stdin
copy 
5
2
-1 -1
4
-1 2 -3 4
8
9 4 11 5 7 9 12 3
20
-49 -23 -56 -90 21 -66 -12 -32 -28 -26 -85 -45 -9 -63 -29 1 5 -48 -63 -54
30
-109 -83 -16 -50 19 -26 -72 8 12 -86 -45 -5 -69 -123 11 -59 45 -8 -123 -114 41 -146 -48 3 -58 32 -129 -34 -32 -55
stdout
copy 
Case #1: 1
Case #2: -15
Case #3: 164
Case #4: 2332
Case #5: -20042
https://ideone.com/oi6TEl
language:
C++14 (gcc 8.3)
created:
5 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!