AcWing 3617. 子矩形计数
原题链接
中等
作者:
今天AC了吗giao
,
2021-06-02 20:15:57
,
所有人可见
,
阅读 334
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 40010;
int a[N],b[N];
int s1[N],s2[N];
int n,m,k;
void work(int a[],int s[],int n)
{
for(int i = 0,j = 0; i < n; i ++)
if(a[i])
{
j ++;
s[1] ++, s[j + 1] --;
}
else j = 0;
for(int i = 1;i <= n; i ++) s[i] += s[i - 1];
}
int main()
{
cin >> n >> m >> k;
for(int i = 0; i < n; i ++) cin >> a[i];
for(int i = 0; i < m; i ++) cin >> b[i];
work(a,s1,n);
work(b,s2,m);
LL res = 0;
for(int i = 1; i <= n; i ++ )
{
if(k % i) continue;
int j = k / i;
if(j > m) continue;
res += s1[i] * s2[j];
}
cout << res << endl;
return 0;
}