Submission #855561

#	Time	Username	Problem	Language	Result	Execution time	Memory
855561		tvladm2009	Count Squares (CEOI19_countsquares)	C++17	100 / 100	1379 ms	158856 KiB

countsquares

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1500 + 7;
int x[N], y[N];

int main() {
#ifdef ONPC
  freopen("input.txt", "r", stdin);
#else
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> y[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> x[i];
  }
  map<int, int> cntY, cntX;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
      cntY[y[i] - y[j]]++;
    }
  }
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j < i; j++) {
      cntX[x[i] - x[j]]++;
    }
  }
  ll sol = 0;
  for (auto &it : cntY) {
    sol += (ll) cntY[it.first] * cntX[it.first];
  }
  cout << sol << "\n";
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 40 / 40
• Subtask 3: 53 / 53