Submission #631002

#	Time	Username	Problem	Language	Result	Execution time	Memory
631002		fadyscube	Catfish Farm (IOI22_fish)	C++17	0 / 100	750 ms	2097152 KiB

fish

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

#define ll long long

vector<vector<int>> v = {{-1}};
ll ans = 0;
int prev_index = -1;
int prev_limit = -1;

ll max_weights (int n, int m, vector<int> x, vector<int> y, vector<int> w) {
	vector<vector<int>> v2 = {{-1}};
	if (v == v2) {
		vector<vector<int>> v3(n, vector<int>(n, 0));
		v = v3;
		for (int i = 0; i < m; i++)
			v[x[i]][y[i]] = w[i];
	}
	// base case
	int count = 0;
	for (int i = 0; i < n; i++)
		if (v[i].size() > n) count++;

	// cout << count << endl;
	if (count >= n-1) {
		return ans;
	}

	// output variables
	// ll ans = 0;
	// prosess input


	// get max weight column
	vector<pair<int, int>> mxs(n);
	for (int i = 0; i < n; i++) {
		if (v[i].size() == n)
			mxs[i] = make_pair(accumulate(v[i].begin(), v[i].end(), 0), i);
		else
			mxs[i] = make_pair(-1, -1);
	}

	auto mx_pair = max_element(mxs.begin(), mxs.end());
	auto mx = mx_pair->second; // index
	ll mx_sum = mx_pair->first; // sum
	// assign pier column to the min weight column from the two adjacents ones
	int mn; // index
	if (0 <= mx+1 && mx+1 < n && 0 <= mx-1 && mx-1 < n) {
		mn = min(mxs[mx-1], mxs[mx+1]).second;
		if (mxs[mx-1].second == -1 && mxs[mx+1].second == -1) {
			v[mx].push_back(0);
			prev_index = -1;
			prev_limit = -1;
			return max_weights(n, m, x, y, w);
		} else if (mxs[mx-1].second == -1) {
			mn = mxs[mx+1].second;
		} else if (mxs[mx+1].second == -1) {
			mn = mxs[mx-1].second;
		} else {
			mn = min(mxs[mx+1], mxs[mx-1]).second;
		}
	} else if (0 <= mx+1 && mx+1 < n) {
		if (mxs[mx+1].second == -1) {
			v[mx].push_back(0);
			prev_index = -1;
			prev_limit = -1;
			return max_weights(n, m, x, y, w);
		}
		mn = mxs[mx+1].second;
	} else {
		if (mxs[mx-1].second == -1) {
			v[mx].push_back(0);
			prev_index = -1;
			prev_limit = -1;
			return max_weights(n, m, x, y, w);
		}
		mn = mxs[mx-1].second;
	}

	int other = -1; // index
	int other_sum = 0; // sum
	if (mn-1 == mx && 0 <= mn+1 && mn+1 < n) {
		other_sum = accumulate(v[mn+1].begin(), v[mn+1].end(), 0);
		other = mn+1;
	} else if (mn+1 == mx && 0 <= mn-1 && mn-1 < n) {
		other_sum = accumulate(v[mn-1].begin(), v[mn-1].end(), 0);
		other = mn-1;
	}


	int limit = 0;
	for (int i = n-1; i >= 0; i--) {
		if (other != -1) {
			if (v[mx][i] > 0 || v[other][i] > 0) {
				limit = i+1;
				break;
			}
		} else {
			if (v[mx][i] > 0) {
				limit = i+1;
				break;
			}
		}
	}

	// turn max weight column and pier column into zeros
	if (prev_index == mn && prev_limit != -1 && prev_limit != -1) {
		if (prev_limit <= limit) {
			v[mn].push_back(0);
			return max_weights(n, m, x, y, w);
		}
	}

	ans += mx_sum;
	ans += other_sum;
	fill(v[mn].begin(), v[mn].begin()+limit-1, 0);
	v[mn].push_back(0);
	fill(v[mx].begin(), v[mx].end(), 0);
	if (other != -1) fill(v[other].begin(), v[other].end(), 0);

	// go to the next max column
	return max_weights(n, m, x, y, w);
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:26:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   if (v[i].size() > n) count++;
      |       ~~~~~~~~~~~~^~~
fish.cpp:41:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |   if (v[i].size() == n)
      |       ~~~~~~~~~~~~^~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16