Submission #770625

#	Time	Username	Problem	Language	Result	Execution time	Memory
770625		josanneo22	Catfish Farm (IOI22_fish)	C++17	100 / 100	110 ms	20904 KiB

fish

//#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 500;
vector<ll> col[maxn];
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
	//两个情况：用i-1行还是不用
	for (int i = 0; i < m; i++) col[x[i]].push_back(i); 
	for (int i = 0; i < n; i++) {
		sort(col[i].begin(), col[i].end(), [&](int i, int j) {
			return y[i] < y[j];
		});
	}
	vector<ll> up_max(n), down_max(n), up(m), down(m);
	//up_max表示最高能拿多少，down_max相似
	//up[i] 还表示若做墙壁在第i个点最高能拿多少，down[i]相似
	for (int i = 0; i < n; i++) {
		if (col[i].size() == 0) {
			if (i == 0) up_max[i] = down_max[i] = 0;
			else up_max[i] = up_max[i - 1], down_max[i] = down_max[i - 1];
			continue;
		}
		//第一种情况：假装删除第i-1行来做
		ll mx = (i < 2 ? 0LL : max(up_max[i - 2], down_max[i - 1]));
		for (int j = 0; j < col[i].size(); j++) {
			int now = col[i][j];
			if (j == 0) up[now] = mx + w[now];
			else up[now] = up[col[i][j-1]] + w[now];
		}
		if (i > 0) {
			mx = (i < 2 ? 0LL : max(up_max[i - 2], down_max[i - 2]));
			for (int j = col[i].size() - 1; j >= 0; j--) {
				int now = col[i][j], above = (j < col[i].size() - 1 ? col[i][j + 1]: -1);
				if (above==-1) down[now] = mx + w[now];
				else down[now] = down[above] + w[now];
			}
		}
		//第二种：利用i-1行做墙壁
		if (i > 0 && col[i-1].size()) {
			int p = -1;
			for (int j = 0; j < col[i].size(); j++) {
				int now = col[i][j], below = (j >= 1 ? col[i][j - 1] : -1), x = col[i - 1].size();
				while (p<x-1 && y[col[i - 1][p + 1]] < y[now]) p++;
				if (p == -1) continue;
				if (below == -1) up[now] = max(up[now], up[col[i - 1][p]] + w[now]);
				else up[now] = max(up[now], max(up[below], up[col[i - 1][p]]) + w[now]);
			} 
			p = col[i - 1].size();
			for (int j = col[i].size() - 1; j >= 0; j--) {
				int now = col[i][j], above = (j < col[i].size() - 1 ? col[i][j + 1] : -1);
				while (p > 0 && y[col[i - 1][p - 1]] > y[now]) p--;
				if (p == col[i-1].size()) continue;
				if (above == -1) down[now] = max(down[now], down[col[i - 1][p]] + w[now]);
				else down[now] = max(down[now], max(down[above], down[col[i - 1][p]]) + w[now]);
			}
		}
		if (i == 0) {
			up_max[i] = up[col[i][col[i].size() - 1]];
			down_max[i] = down[col[i][0]];
		}
		else {
			up_max[i] = max(up_max[i-1],up[col[i][col[i].size() - 1]]);
			down_max[i] = max(down_max[i-1],down[col[i][0]]);
		}
	}
	return max(down_max[n - 1], up_max[n - 2]);
}

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:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (int j = 0; j < col[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
fish.cpp:34:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     int now = col[i][j], above = (j < col[i].size() - 1 ? col[i][j + 1]: -1);
      |                                   ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for (int j = 0; j < col[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
fish.cpp:51:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     int now = col[i][j], above = (j < col[i].size() - 1 ? col[i][j + 1] : -1);
      |                                   ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:53:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     if (p == col[i-1].size()) continue;
      |         ~~^~~~~~~~~~~~~~~~~~

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