Submission #1119520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119520		vjudge1	Count Squares (CEOI19_countsquares)	C++17	100 / 100	963 ms	93416 KiB

countsquares

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <list>
#include <array>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <iomanip>
#include <unordered_map>
using namespace std;

#define sx (int)s.size()
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL);}
#define f first
#define s second
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
const int N = 1e6;
int h, v, y[N], x[N];
int ans = 0;
// string s;
// int mx() {
	// int temp = s.size();
	// unordered_map <string, int> palindrom;
	// int mxv = 0;
	// auto cnt = [&] (int l, int r) {
		// while (l >= 0 && r < temp && s[l] == s[r]) {
			// string pal = s.substr(l, r - l + 1);
			// palindrom[pal]++;
			// l--;
			// r++;
		// }
	// };
	// for (int i = 0; i < temp; ++i) {
		// cnt(i, i);
		// cnt(i, i + 1);
	// }
	// for (auto i : palindrom) {
		// int nw = i.s * (i.f).size();
		// mxv = max(mxv, nw);
	// }
	// return mxv;
// }
int calc() {
	unordered_map <int, int> yd, xd;
	for (int i = 1; i <= h; ++i) {
		for (int j = i + 1; j <= h; ++j) {
			yd[y[j] - y[i]]++;
		}
	}
	for (int i = 1; i <= v; ++i) {
		for (int j = i + 1; j <= v; ++j) {
			xd[x[j] - x[i]]++;
		}
	}
	for (auto i : yd) {
		if (xd.count(i.f)) {
			ans += i.s * xd[i.f];
		}
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	// cin >> s;
	// cout<<mx();
	cin >> h >> v;
	for (int i = 1; i <= h; ++i) {
		cin >> y[i];
	}
	for (int i = 1; i <= v; ++i) {
		cin >> x[i];
	}
	cout<<calc();
    return 0;
}

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