Codeforces Round #626 （Div. 2） B. Count Subrectangles

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 int a[100100],b[100100];
 6 int c[100100];
 7 
 8 int main()
 9 {
10     int n,m,k;
11     cin>>n>>m>>k;
12     for(int i=0;i<n;i++) cin>>a[i];
13     for(int i=0;i<m;i++) cin>>b[i];
14     int p=0;
15     for(int i=1;i*i<=k;i++){
16         if(k%i==0){
17             c[p++]=i;
18             if(i==k/i) continue;
19             c[p++]=k/i;
20         }
21     }
22     ll ans=0;
23     for(int i=0;i<p;i++){
24         int cnt=0;
25         ll x=0,y=0;
26         for(int j=0;j<n;j++){
27             if(a[j]==1) cnt++;
28             else cnt=0;
29             if(cnt==c[i]) cnt--,x++;
30         }
31         cnt=0;
32         for(int j=0;j<m;j++){
33             if(b[j]==1) cnt++;
34             else cnt=0;
35             if(cnt==k/c[i]) cnt--,y++;
36         }
37         ans=ans+x*y;
38     }
39     cout<<ans<<endl;
40     return 0;
41 }