fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define endl '\n'
  4. #define all(v) v.begin(), v.end()
  5. #define rall(v) v.rbegin(), v.rend()
  6. #define input(v) for(auto &a:v)cin>>a;
  7. #define output(v) for(auto &a:v)cout<<a<<" ";
  8. #define outputel(v) for(auto &a:v)cout<<a<<" ";cout<<endl;
  9. #define mem(arr) memset(arr,0,sizeof(arr));
  10. #define LSone(x) (x & (-x))
  11. #define YNO(x) cout<<(x ? "YES" : "NO")<<endl;
  12. #define sz(x) (ll)x.size()
  13. #define multpush(s,x) for(auto &c:x)s.push_back(c);
  14. #define vc vector<char>
  15. #define y second
  16. #define x first
  17. #define int ll
  18. using namespace std;
  19.  
  20. void fastio() {
  21. #ifdef LOCAL
  22.     freopen("input.txt", "r",stdin);
  23. #else
  24.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  25. #endif
  26. }
  27.  
  28. const ll MOD = 1e9 + 7;
  29. const ll INF = 1e9 + 50;
  30. const int MXS = 1e5 + 5;
  31. const int NLOGN = 4e6 + 5;
  32. int prefa[105],prefb[105],pref[105],a[105],b[105];
  33. int n;
  34. int memo[10010][105];
  35. int vis[10010][105];
  36. int tc = 1;
  37. int best(int idx,int sum) {
  38.     if (idx == n+1)
  39.         return 0;
  40.     int sumb = pref[idx-1] - sum;
  41.     if (vis[sum][idx] == tc)
  42.         return memo[sum][idx];
  43.     vis[sum][idx] = tc;
  44.     return memo[sum][idx] = min(best(idx+1,sum+a[idx]) + a[idx] * sum * 2 + b[idx] * sumb*2,
  45.                                 best(idx+1,sum+b[idx]) + a[idx] * sumb* 2 + b[idx] * sum *2);
  46. }
  47. void solve() {
  48.     tc++;
  49.     cin>>n;
  50.     for (int i = 1;i<=n;i++) {
  51.         cin>>a[i];
  52.         prefa[i] = prefa[i-1] + a[i];
  53.     }
  54.     for (int i = 1;i<=n;i++) {
  55.         cin>>b[i];
  56.         prefb[i] = prefb[i-1] + b[i];
  57.     }
  58.     for (int i = 1;i<=n;i++) {
  59.         pref[i] =prefa[i] + prefb[i];
  60.     }
  61.     int sum = 0;
  62.     for (int i = 1;i<=n;i++) {
  63.         sum+=a[i]*a[i]*(n-1);
  64.         sum+=b[i]*b[i]*(n-1);
  65.     }
  66.     cout<<best(1,0)+sum<<endl;
  67.  
  68.  
  69.  
  70.  
  71.  
  72. }
  73.  
  74. signed main() {
  75.     fastio();
  76.     int i = 1;
  77.     cin>>i;
  78.     while (i--)
  79.         solve();
  80. }
  81.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/8qCvWF
language:
C++14 (gcc 8.3)
created:
3 hours ago
visibility:
public

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!