Submission #770588

#	Time	Username	Problem	Language	Result	Execution time	Memory
770588		josanneo22	Catfish Farm (IOI22_fish)	C++17	100 / 100	136 ms	27244 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) {
	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(m, 0), down(m, 0);
	vector<ll> up_max(n, 0), down_max(n, 0);
	for(int i = 0; i < n; i++) {
		if (col[i].size() == 0) {//empty col
			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;
		}
		ll mx = (i < 2) ? 0LL : max(up_max[i - 2], down_max[i - 1]);
		for (int j = 0; j < col[i].size(); j++) {
			if (j == 0) up[col[i][0]] = mx + w[col[i][0]];
			else up[col[i][j]] = w[col[i][j]] + up[col[i][j - 1]];
		}
		if (i > 0) {
			//delete i-1 column
			mx = (i < 2) ? 0LL : max(up_max[i - 2], down_max[i - 2]);//must make sure that it has at last two columns in front
			for (int j = col[i].size() - 1; j >= 0; --j) {
				if (j == col[i].size() - 1) down[col[i][j]] = mx + w[col[i][j]];
				else  down[col[i][j]] = down[col[i][j + 1]] + w[col[i][j]]; 
			}
		}
        //case 2: actually using the previous column
        if (i > 0 && col[i - 1].size() > 0) {//make sure that i-1 col isn't empty
            int p=-1, x = col[i - 1].size();
            for (int j = 0; j < col[i].size(); j++) {
                //p records last index of col that has y coordinate less than current calculation
                while (p < x - 1 && y[col[i - 1][p + 1]] < y[col[i][j]]) p++;
                if (p == -1) continue;//nothing
                if (j == 0) up[col[i][j]] = max(up[col[i][j]], up[col[i - 1][p]] + w[col[i][j]]);
                else {
                    up[col[i][j]] = max({ up[col[i][j]],//just put to update max
                        up[col[i - 1][p]] + w[col[i][j]],//build on last col, with height p
                        up[col[i][j - 1]] + w[col[i][j]] });// build strictly below it
                }
            }
            p = x;//this is down and almost similar just from top to bottom instead
            if (i > 1) {
                for (int j = col[i].size() - 1; j >= 0; j--) {
                    while (p > 0 && y[col[i - 1][p - 1]] > y[col[i][j]]) p--;
                    if (p == x) continue;
                    if (j == col[i].size() - 1) down[col[i][j]] = max(down[col[i][j]], down[col[i - 1][p]] + w[col[i][j]]);
                    else {
                        down[col[i][j]] = max(down[col[i][j]],
                            max(down[col[i - 1][p]], down[col[i][j + 1]]) + w[col[i][j]]);
                    }
                }
            }
        }
        //update max
        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(up_max[n - 2], down_max[n - 1]);
}

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:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     if (j == col[i].size() - 1) down[col[i][j]] = mx + w[col[i][j]];
      |         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:40:31: 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:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                     if (j == col[i].size() - 1) down[col[i][j]] = max(down[col[i][j]], down[col[i - 1][p]] + w[col[i][j]]);
      |                         ~~^~~~~~~~~~~~~~~~~~~~

• 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