-
Notifications
You must be signed in to change notification settings - Fork 0
/
1323B.cpp
71 lines (71 loc) · 1.76 KB
/
1323B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll n,m,k;scanf("%lld %lld %lld",&n,&m,&k);
ll a[n],b[m];
for(int i=0;i<n;++i) scanf("%lld",a+i);
for(int i=0;i<m;++i) scanf("%lld",b+i);
vector<pair<ll,ll>> afr,bfr;
int fre[max(n,m)+100];
for(int i=1;i<=n;++i) fre[i] = 0;
int s = 0;
for(int i=0;i<n;++i){
if(a[i]) ++s;
else{
fre[s]++;
s = 0;
}
}
fre[s]++;
ll mx = 0;
for(ll i=1;i<=n;++i){
if(fre[i]){
afr.push_back({i,fre[i]});
mx = max(mx,i);
}
}
for(int i=1;i<=m;++i) fre[i] = 0;
s = 0;
for(int i=0;i<m;++i){
if(b[i]) ++s;
else{
fre[s]++;
s = 0;
}
}
fre[s]++;
for(ll i=1;i<=m;++i){
if(fre[i]){
bfr.push_back({i,fre[i]});
mx = max(mx,i);
}
}
vector<ll> div;
for(ll i=1; i*i<=k && i<=mx;++i){
if(k%i== 0 &&k/i <= mx) div.push_back(i);
}
// cout<<"mx: "<<mx<<"\n";
// for(auto d:div) cout<<d<<" ";
ll res = 0;
for(int i=0;i<afr.size();++i){
for(int j=0;j<bfr.size();++j){
ll curr = 0;
ll width = bfr[j].first;
ll height = afr[i].first;
for(int i=0;i<div.size();++i){
ll a = div[i];
ll b = k/div[i];
ll frw = max(0LL,width-b+1);
ll frh = max(0LL,height-a+1);
curr += frw*frh;
if(a == b) continue;
frw = max(0LL,width-a+1);
frh = max(0LL,height-b+1);
curr += frw*frh;
}
res += curr*afr[i].second*bfr[j].second;
}
}
printf("%lld\n",res);
}