Submission #770603

#	Time	Username	Problem	Language	Result	Execution time	Memory
770603		josanneo22	Catfish Farm (IOI22_fish)	C++17	0 / 100	32 ms	20940 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[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];
		}
		//第一种情况：假装删除第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],below=(j>=1?col[i][j-1]:-1);
			if (j == 0) up[now] = mx + w[now];
			else up[now] = up[below] + 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 (j == col[i].size() - 1) down[now] = mx + w[now];
				else down[now] = down[above] + w[now];
			}
		}
		//第二种：利用i-1行做墙壁
		if (i > 0) {
			for (int j = 0; j < col[i].size(); j++) {
				int now = col[i][j], p = -1, below = (j >= 1 ? col[i][j - 1] : -1);
				while (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]);
			}
			for (int j = col[i].size() - 1; j >= 0; j--) {
				int now = col[i][j], p = col[i].size(), below = (j < col[i].size() ? col[i][j+1] : -1); 
				while (y[col[i - 1][p-1]] < y[now]) p--;
				if (p == col[i].size()) continue;
				if (below == -1) down[now] = max(down[now], down[col[i - 1][p]] + w[now]);
				else down[now] = max(down[now], max(down[below], down[col[i - 1][p]]) + w[now]);
			}
		}
		for (int j = 0; j < col[i].size(); j++) {
			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:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for (int j = 0; j < col[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
fish.cpp:33:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     int now = col[i][j], above = (j < col[i].size() - 1 ? col[i][j + 1]: -1);
      |                                   ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:34:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     if (j == col[i].size() - 1) down[now] = mx + w[now];
      |         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for (int j = 0; j < col[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
fish.cpp:48:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     int now = col[i][j], p = col[i].size(), below = (j < col[i].size() ? col[i][j+1] : -1);
      |                                                      ~~^~~~~~~~~~~~~~~
fish.cpp:50:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     if (p == col[i].size()) continue;
      |         ~~^~~~~~~~~~~~~~~~
fish.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (int j = 0; j < col[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~

• 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