ICPC 模擬国内2007D スクウェア・ルート AOJ2015

judge.u-aizu.ac.jp

あらかじめ考えられるすべての辺の長さをキーに、その長さの出現回数を値にして保存しておけばよい。大きめの配列を使えばいいがmapを使った。

#include <bits/stdc++.h>

using namespace std;


int n,m;
int h[1600],w[1600];


int main(){
    while(true){
        cin >> n >> m;
        if(n + m == 0)break;
        for(int i = 1;i <= n;i++)cin >> h[i];
        for(int j = 1;j <= m;j++)cin >> w[j];
        map<int, int> d;
        for(int i = 1;i <= m;i++){
            int sum = 0;
            for(int j = i;j <= m;j++){
                sum += w[j];
                d[sum]++;
            }
        }
        int ans = 0;
        for(int i = 1;i <= n;i++){
            int sum = 0;
            for(int j = i;j <= n;j++){
                sum += h[j];
                ans += d[sum];
            }
        }
        cout << ans << endl;
    }
}