fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define dbg(var) cout<<#var<<"="<<var<<" "
  5. #define nl cout<<"\n"
  6. #define fr(i,n) for(int i=0;i<n;i++)
  7. #define rep(i,a,n) for(int i = a; i <= n; i++)
  8. #define per(i,a,n) for(int i = a; i >= n; i--)
  9. #define vi vector<int>
  10. #define pb push_back
  11. #define itr(i,v) for(auto &i:v)
  12. #define all(v) v.begin(),v.end()
  13. #define sz(v) (int)(v.size())
  14. #define int long long
  15. #define kill(x) {cout << x << "\n"; return;}
  16.  
  17. const int N = 1005,S = 2*10010, offset = 10000, mod = 1e9 + 7;
  18. int a[N],ways_left[S],ways_right[S],ans=0,pfxa[N],b[N], pfxb[N];
  19. int dp[S][2];
  20. int get_sum(int l,int r){return max(pfxa[r] - pfxa[l-1], pfxb[r] - pfxb[l-1]);}
  21. void rec(int left,int right){
  22.     if(left == right) return;
  23.     int mid = (left + right)/2 ;
  24.     int mnS = max(get_sum(left,mid), get_sum(mid+1,right));
  25.     int offsetS = mnS;
  26.     for(int i = -mnS; i <= mnS; i++) 
  27.         dp[i + offsetS][0] = dp[i + offsetS][1] 
  28.     = ways_left[i + offsetS]  = ways_right[i + offsetS] = 0;
  29.     dp[0 + offsetS][0] = 1;
  30.     int ptr = 0;
  31.     rep(i,mid+1,right){
  32.         for(int curS = -mnS; curS <= mnS; curS++)
  33.             dp[curS + offsetS][ptr ^ 1] = 0;
  34.         for(int curS = -mnS; curS <= mnS; curS++){
  35.             if(a[i] + curS >= -mnS and a[i] + curS <= mnS){
  36.                 dp[a[i] + curS + offsetS][ptr^1] += dp[curS + offsetS][ptr];
  37.                 if(dp[a[i] + curS + offsetS][ptr^1] >= mod) 
  38.                     dp[a[i] + curS + offsetS][ptr^1] -= mod;
  39.             }
  40.             if(-b[i] + curS >= -mnS and -b[i] + curS <= mnS){
  41.                 dp[-b[i] + curS + offsetS][ptr ^ 1] += dp[curS + offsetS][ptr];
  42.                 if(dp[-b[i] + curS + offsetS][ptr^1] >= mod) 
  43.                     dp[-b[i] + curS + offsetS][ptr^1] -= mod;
  44.             }
  45.         }
  46.         ptr ^= 1;
  47.         for(int curS = -mnS; curS <= mnS; curS++){
  48.             ways_left[curS + offsetS] += dp[curS + offsetS][ptr];
  49.             if(ways_left[curS + offsetS] >= mod) 
  50.                 ways_left[curS + offsetS] -= mod;
  51.         }
  52.     }
  53.     for(int i = -mnS; i <= mnS; i++) 
  54.         dp[i + offsetS][0] = dp[i + offsetS][1] = 0;
  55.     ptr = 0;
  56.     dp[0 + offsetS][0] = 1;
  57.     per(i,mid,left){
  58.         for(int curS = -mnS; curS <= mnS; curS++)
  59.             dp[curS + offsetS][ptr ^ 1] = 0;
  60.         for(int curS = -mnS; curS <= mnS; curS++){
  61.             if(a[i] + curS >= -mnS and a[i] + curS <= mnS){
  62.                 dp[a[i] + curS + offsetS][ptr^1] += dp[curS + offsetS][ptr];
  63.                 if(dp[a[i] + curS + offsetS][ptr^1] >= mod) 
  64.                     dp[a[i] + curS + offsetS][ptr^1] -= mod;
  65.             }
  66.             if(-b[i] + curS >= -mnS and b[i] + curS <= mnS){
  67.                 dp[-b[i] + curS + offsetS][ptr ^ 1] += dp[curS + offsetS][ptr];
  68.                 if(dp[-b[i] + curS + offsetS][ptr^1] >= mod) 
  69.                     dp[-b[i] + curS + offsetS][ptr^1] -= mod;
  70.             }
  71.         }
  72.         ptr ^= 1;
  73.         for(int curS = -mnS; curS <= mnS; curS++){
  74.             ways_right[curS + offsetS] += dp[curS + offsetS][ptr];
  75.             if(ways_right[curS + offsetS] >= mod) 
  76.                 ways_right[curS + offsetS] -= mod;
  77.         }
  78.     }
  79.     for(int curS = -mnS; curS <= mnS; curS++){
  80.         ans += ways_left[curS + offsetS] * ways_right[-curS + offsetS];
  81.         ans %= mod;
  82.     }
  83.     rec(left, mid);
  84.     rec(mid+1, right);
  85. }
  86. void solve(){
  87.    int n; cin >> n;
  88.    rep(i,1,n) cin >> a[i], pfxa[i] = pfxa[i-1] + a[i];
  89.    rep(i,1,n) cin >> b[i], pfxb[i] = pfxb[i-1] + b[i];
  90.    rec(1,n);
  91.    cout << ans << "\n";
  92.  
  93. }
  94.  
  95. int32_t main()
  96. {
  97.    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  98.    // int tst; cin >> tst; while(tst--)
  99.    {
  100.        solve();
  101.    }
  102. }
Success #stdin #stdout 0.01s 5520KB
comments (?)
stdin
copy 
5
1 2 3 4 5
1 2 3 4 5
stdout
copy 
6
https://ideone.com/BHM3vP
language:
C++14 (gcc 8.3)
created:
3 years 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!