fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cmath>
  5. using namespace std;
  6.  
  7. #define ll long long int
  8.  
  9. ll binary(vector<ll> a, ll val){
  10.     ll start = 0, end = a.size()-1;
  11.     ll mid;
  12.     if(val>a[start]) return -1;
  13.     while(start<=end){
  14.         mid = (start+end)/2;
  15.         if(a[mid]<val){
  16.             end = mid-1;
  17.             continue;
  18.         }
  19.         else if((mid==(a.size()-1))||(a[mid]>=val&&a[mid+1]<val)) break;
  20.         else{
  21.             start = mid+1;
  22.             continue;
  23.         }
  24.     }
  25.     return mid;
  26. }
  27.  
  28. int main(){
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(NULL);
  31.     ll n, m, k;
  32.     cin>>n>>m>>k;
  33.     bool a[n], b[m];
  34.     for(auto& it:a) cin>>it;
  35.     for(auto& it:b) cin>>it;
  36.     ll j = -1;
  37.     vector<ll> at, bt;
  38.     for(ll i=0; i<n; i++){
  39.         if(a[i]==0&&j!=-1){
  40.             at.push_back(i-j);
  41.             j = -1;
  42.         }
  43.         else if(a[i]==1&&j==-1) j = i;
  44.     }
  45.     if(j!=-1){
  46.         at.push_back(n-j);
  47.         j = -1;
  48.     }
  49.     for(ll i=0; i<m; i++){
  50.         if(b[i]==0&&j!=-1){
  51.             bt.push_back(i-j);
  52.             j = -1;
  53.         }
  54.         else if(b[i]==1&&j==-1) j = i;
  55.     }
  56.     if(j!=-1) bt.push_back(m-j);
  57.     sort(at.begin(), at.end(), greater<ll>());
  58.     sort(bt.begin(), bt.end(), greater<ll>());
  59.     vector<ll> f;
  60.     for(ll i=1; i<=int(sqrt(k)); i++){
  61.         if(k%i==0) f.push_back(i);
  62.     }
  63.     ll v1, v2, t1, t2, count;
  64.     count=0;
  65.     for(ll i=0; i<f.size(); i++){
  66.         v1 = binary(at, f[i]);
  67.         v2 = binary(bt, k/f[i]);
  68.         t1 = 0;
  69.         for(ll h=0; h<=v1; h++){
  70.             t1 += at[h]-f[i]+1;
  71.         }
  72.         t2 = 0;
  73.         for(ll h=0; h<=v2; h++){
  74.             t2 += bt[h]-(k/f[i])+1;
  75.         }
  76.         count += t1*t2;
  77.         if(f[i]*f[i]==k) continue;
  78.         v1 = binary(at, k/f[i]);
  79.         v2 = binary(bt, f[i]);
  80.         t1 = 0;
  81.         for(ll h=0; h<=v1; h++){
  82.             t1 += at[h]-f[i]+1;
  83.         }
  84.         t2 = 0;
  85.         for(ll h=0; h<=v2; h++){
  86.             t2 += bt[h]-(k/f[i])+1;
  87.         }
  88.         count += t1*t2;
  89.     }
  90.     cout<<count;
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 4468KB
comments (?)
stdin
copy 
50 50 6
1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1
1 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0
stdout
copy 
912
https://ideone.com/FudOsK
language:
C++14 (gcc 8.3)
created:
4 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!