Submission #1227132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227132		doblynguyen	Garden (JOI23_garden)	C++20	0 / 100	3094 ms	10204 KiB

garden

#include <bits/stdc++.h>
using namespace std;

#define task "JOI23_garden"
#define ll long long
#define ft first
#define sc second
#define ii pair <int, int>

const int N = 5e5+5, inf = 1e9+5;
int n, m, d;
ii a[N], b[N];

void init(){
	cin >> n >> m >> d;
	for (int i = 1; i <= n; i++) cin >> a[i].ft >> a[i].sc;
	for (int i = 1; i <= m; i++) cin >> b[i].ft >> b[i].sc;
}

namespace Subtask_1{
	int type[N], ans = inf;

	void calc(){
		vector <int> vtA, vtB;
		for (int i = 1; i <= n; i++){
			vtA.push_back(a[i].ft % d);
			vtB.push_back(a[i].sc % d);
		}
		for (int i = 1; i <= m; i++){
			if (type[i]) vtB.push_back(b[i].sc % d);
			else vtA.push_back(b[i].ft % d);
		}

		sort(vtA.begin(), vtA.end());
		sort(vtB.begin(), vtB.end());
		int maxA = d - vtA.back() - 1 + vtA.front(), maxB = d - vtB.back() - 1 + vtB.front();
		for (int i = 1; i < vtA.size(); i++) maxA = max(maxA, vtA[i] - vtA[i - 1] - 1);
		for (int i = 1; i < vtB.size(); i++) maxB = max(maxB, vtB[i] - vtB[i - 1] - 1);
		maxA = d - maxA; maxB = d - maxB;
		// cerr << maxA << " " << maxB << "\n";
		ans = min(ans, maxA * maxB);
	}

	void rcs(int pos){
		if (pos > m){
			calc();
			return;
		}
		for (int i = 0; i <= 1; i++){
			type[pos] = i;
			rcs(pos + 1);
		}
	}

	void solve(){
		rcs(1);
		cout << ans;
	}
}

void solution(){
	if (m <= 8) Subtask_1::solve();
}

signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    if(ifstream(task".inp")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    init();
    solution();

    return 0;
}

// --------------- Nvr3xst ---------------

// ⡇⡆⣐⢕⢕⢕⢕⢕⢕⢕⢕⠅⢗⢕⢕⢕⢕⢕⢕⢕⠕⠕⢕⢕⢕⢕⢕⢕⢕⢕⢕
// ⡇⢐⢕⢕⢕⢕⢕⣕⢕⢕⠕⠁⢕⢕⢕⢕⢕⢕⢕⢕⠅⡄⢕⢕⢕⢕⢕⢕⢕⢕⢕
// ⡇⢕⢕⢕⢕⢕⠅⢗⢕⠕⣠⠄⣗⢕⢕⠕⢕⢕⢕⠕⢠⣿⠐⢕⢕⢕⠑⢕⢕⠵⢕
// ⡇⢕⢕⢕⢕⠁⢜⠕⢁⣴⣿⡇⢓⢕⢵⢐⢕⢕⠕⢁⣾⢿⣧⠑⢕⢕⠄⢑⢕⠅⢕
// ⡇⢕⢕⠵⢁⠔⢁⣤⣤⣶⣶⣶⡐⣕⢽⠐⢕⠕⣡⣾⣶⣶⣶⣤⡁⢓⢕⠄⢑⢅⢑
// ⡇⠍⣧⠄⣶⣾⣿⣿⣿⣿⣿⣿⣷⣔⢕⢄⢡⣾⣿⣿⣿⣿⣿⣿⣿⣦⡑⢕⢤⠱⢐
// ⡇⢠⢕⠅⣾⣿⠋⢿⣿⣿⣿⠉⣿⣿⣷⣦⣶⣽⣿⣿⠈⣿⣿⣿⣿⠏⢹⣷⣷⡅⢐
// ⡇⣔⢕⢥⢻⣿⡀⠈⠛⠛⠁⢠⣿⣿⣿⣿⣿⣿⣿⣿⡀⠈⠛⠛⠁⠄⣼⣿⣿⡇⢔
// ⡇⢕⢕⢽⢸⢟⢟⢖⢖⢤⣶⡟⢻⣿⡿⠻⣿⣿⡟⢀⣿⣦⢤⢤⢔⢞⢿⢿⣿⠁⢕
// ⡇⢕⢕⠅⣐⢕⢕⢕⢕⢕⣿⣿⡄⠛⢀⣦⠈⠛⢁⣼⣿⢗⢕⢕⢕⢕⢕⢕⡏⣘⢕
// ⡇⢕⢕⠅⢓⣕⣕⣕⣕⣵⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣷⣕⢕⢕⢕⢕⡵⢀⢕⢕
// ⡇⢑⢕⠃⡈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢃⢕⢕⢕
// ⡇⣆⢕⠄⢱⣄⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⢁⢕⢕⠕⢁
// ⡇⣿⣦⡀⣿⣿⣷⣶⣬⣍⣛⣛⣛⡛⠿⠿⠿⠛⠛⢛⣛⣉⣭⣤⣂⢜⠕⢑⣡⣴⣿

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25