Submission #753592

#	Time	Username	Problem	Language	Result	Execution time	Memory
753592		armand	Catfish Farm (IOI22_fish)	C++17	9 / 100	101 ms	7768 KiB

fish

#include "fish.h"
#include <algorithm>
using namespace std;

long long solve3(int n, int m, vector<int>& x, vector<int>& y, vector<int>& w)
{
	const int N = 1000001;
	int* a = new int [N];
	long long ** b = new long long * [2];
	int i;
	for (i = 0; i < 2; i++)
		b[i] = new long long[N];
	for (i = 0; i < N; i++)
		a[i] = 0;
	for (i = 0; i < m; i++)
		a[x[i]] = w[i];
	b[0][0] = 0; b[1][0] = 0;
	b[0][1] = a[0]; b[1][1] = a[1];
	for (i = 2; i < n; i++) {
		b[0][i] = max(b[1][i - 2] + a[i - 1], b[0][i - 2] + a[i - 1]);
		b[1][i] = max(b[0][i - 1] + a[i], b[1][i - 1]);
	}
	return max(b[0][n - 1], b[1][n - 1]);
}

long long solve2(int n, int m, vector<int>& x, vector<int>& y, vector<int>& w)
{
	int i, j;
	long long suma = 0, sumb = 0, ans, ans2=0, tmp;
	vector< pair<int, int> > a, b;
	for (i = 0; i < m; i++)
		if (x[i] == 0) {
			suma += w[i];
			a.push_back(make_pair(y[i], w[i]));
		}
		else {
			sumb += w[i];
			b.push_back(make_pair(y[i], w[i]));
		}
	ans = suma > sumb ? suma : sumb;
	if (n > 2) {
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());
		ans2 = sumb;
		i = 0; j = 0;
		tmp = ans2;
		for (j = 0; j < b.size(); j++) {
			while (i < a.size() && a[i].first < b[j].first) {
				tmp += a[i].second;
				i++;
			}
			if (tmp > ans2) ans2 = tmp;
			if(i<a.size() && a[i].first == b[j].first)
				tmp += a[i++].second;
			tmp -= b[j].second;
			if (tmp > ans2)
				ans2 = tmp;
		}
		return ans > ans2 ? ans : ans2;
	}
	return ans;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
	std::vector<int> W)
{
	int i;
	bool flag2 = true, flag3=true;
	long long ans = 0;
	for (i = 0; i < M; i++) {
		if (X[i] > 1)
			flag2 = false;
		if (Y[i] > 0)
			flag3 = false;
	}
	if (flag2)
		return solve2(N, M, X, Y, W);
	if (flag3)
		return solve3(N, M, X, Y, W);
	for (i = 0; i < W.size(); i++)
		ans += W[i];
	return ans;
}

Compilation message (stderr)

fish.cpp: In function 'long long int solve2(int, int, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
fish.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (j = 0; j < b.size(); j++) {
      |               ~~^~~~~~~~~~
fish.cpp:48:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    while (i < a.size() && a[i].first < b[j].first) {
      |           ~~^~~~~~~~~~
fish.cpp:53:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    if(i<a.size() && a[i].first == b[j].first)
      |       ~^~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (i = 0; i < W.size(); i++)
      |              ~~^~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 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