Submission #836902

#	Time	Username	Problem	Language	Result	Execution time	Memory
836902		MeGustaElArroz23	Catfish Farm (IOI22_fish)	C++17	0 / 100	1112 ms	2097152 KiB

fish

#include "fish.h"

#include <vector>

#include<bits/stdc++.h>

using namespace std;

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
                      std::vector<int> w) {

#define ll long long
#define vi vector<long long>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vb vector<bool>
#define pii pair<long long,long long>
#define vii vector<pii>
#define vvii vector<vii>
#define pb push_back
#define fi first
#define se second

	vvi posh(n);
	for (int i=0;i<m;i++) posh[x[i]].pb(y[i]-1);
	for (int i=0;i<n;i++) posh[i].pb(n-1);

	for (int i=0;i<n;i++) sort(posh[i].begin(),posh[i].end());

	vvii cats(n);
	for (int i=0;i<m;i++) cats[x[i]].pb(pii{y[i],w[i]});
	//for (int i=0;i<n;i++) cats[i].pb(pii{n,0});

	for (int i=0;i<n;i++) sort(cats[i].begin(),cats[i].end());


	//cerr << "HHHHHHHHHHHHHH\n";

	vvi pref(n,vi(n+1,0));
	for (int i=0;i<n;i++){
		int k=0;
		for (int j=1;j<=n;j++){
			if (k<cats[i].size() && cats[i][k].fi==j-1){
				pref[i][j]=pref[i][j-1]+cats[i][k].se;
				k++;
			}
			else pref[i][j]=pref[i][j-1];
		}
	}

	//cerr << "HHHHHHHHHHHHHH\n";

	vvvi dp(n); //columna, h[i], h[i-1]

	//hago dp[1]

	dp[1]=vvi(posh[1].size(),vi(posh[0].size(),0));

	for (int i=0;i<posh[1].size();i++){
		for (int j=0;j<posh[0].size();j++){
			if (posh[1][i]>posh[0][j]) 
				dp[1][i][j]=pref[0][posh[1][i]+1]-pref[0][posh[0][j]+1];
			else
				dp[1][i][j]=pref[1][posh[0][j]+1]-pref[1][posh[1][i]+1];
		}
	}

	//
	//cerr << "HHHHHHHHHHHHHH\n";

	for (int i=2;i<n;i++){
		dp[i]=vvi(posh[i].size(),vi(posh[i-1].size(),0));
		for (int j=0;j<posh[i].size();j++){ //altura
			for (int k=0;k<posh[i-1].size();k++){ //altura ant
				for (int l=0;l<posh[i-2].size();l++){

					ll ans=dp[i-1][k][l];

					if (posh[i][j]>posh[i-1][k]){
						if (posh[i][j]>posh[i-2][l])
							ans+=pref[i-1][posh[i][j]+1]-pref[i-1][
								max(posh[i-2][l],posh[i-1][k]) +1];
					}
					else
						ans+=pref[i][posh[i-1][k]]-pref[i][posh[i][j]];

					dp[i][j][k]=max(dp[i][j][k],ans);
				}
			}
		}
	}

	//cerr << "HHHHHHHHHHHHHH\n";

	int res=0;
	for (vi v:dp[n-1]){
		for (int b:v) res=max(res,b);
		
	}

	return res;
}

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:43:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (k<cats[i].size() && cats[i][k].fi==j-1){
      |        ~^~~~~~~~~~~~~~~
fish.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i=0;i<posh[1].size();i++){
      |               ~^~~~~~~~~~~~~~~
fish.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int j=0;j<posh[0].size();j++){
      |                ~^~~~~~~~~~~~~~~
fish.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int j=0;j<posh[i].size();j++){ //altura
      |                ~^~~~~~~~~~~~~~~
fish.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for (int k=0;k<posh[i-1].size();k++){ //altura ant
      |                 ~^~~~~~~~~~~~~~~~~
fish.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int l=0;l<posh[i-2].size();l++){
      |                  ~^~~~~~~~~~~~~~~~~

• 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