Submission #799938

#	Time	Username	Problem	Language	Result	Execution time	Memory
799938		LIF	Catfish Farm (IOI22_fish)	C++17	46 / 100	1091 ms	116440 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
#include<unordered_map>
#pragma GCC optimize(3)
typedef long long int ll;
using namespace std;
long long int a[2][300005];
long long int mp[100005][10];
long long int dp[100005][10][10];
long long int s[100005][10];
vector<int> row[300005];
vector<pair<int,int> > vv[300005];
int find(int coll,int high)
{
	int pe = 0;
	for(int i=0;i<vv[coll].size();i++)
	{
		if(high >= vv[coll][i].first) pe += vv[coll][i].second; 
	}
	return pe;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) 
{
	//subtask1:
	bool flag1 = true;
	for(int i=0;i<X.size();i++)if(X[i] %2 != 0)flag1 = false;
	if(flag1 == true)
	{
		long long int su = 0;
		for(int i=0;i<W.size();i++)su += W[i];
		return su;
	}
	//
	//subtask2:
	bool flag2 = true;
	for(int i=0;i<X.size();i++)if(X[i] > 1)flag2 = false;
	if(flag2 == true)
	{
		long long int maxn = -1;
		long long int su = 0;
		for(int i=0;i<X.size();i++)a[X[i]][Y[i]] = W[i];
		if(N > 2)
		{	
			for(int i=0;i<N;i++)su += a[1][i];
			maxn = max(maxn,su);
			for(int i=0;i<N;i++)
			{
				su -= a[1][i];
				su += a[0][i];
				maxn = max(maxn,su);
			} 
			return maxn;
		}
		else
		{
			long long int su1 = 0;
			long long int su2 = 0;
			for(int i=0;i<N;i++)su1 += a[0][i];
			for(int i=0;i<N;i++)su2 += a[1][i];
			return max(su1,su2);
		}
	}	
	
	for(int i=0;i<X.size();i++)X[i] += 1;
	for(int i=0;i<Y.size();i++)Y[i] += 1;
	//subtask3:
	bool flag34 = true;
	for(int i=0;i<M;i++)
	{
		if(Y[i] > 10)flag34 = false;
	}
	long long int zero = 0;
	if(flag34 == true)
	{
		for(int i=0;i<M;i++)mp[X[i]][Y[i]] = W[i];
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=9;j++)s[i][j] = s[i][j-1] + mp[i][j];
		}
		long long int maxn = -1;
		for(int i=1;i<=N;i++)
		{
			for(int j=0;j<=min(N,9);j++)
			{
				for(int k=0;k<=min(N,9);k++)
				{
					for(int l=0;l<=min(N,9);l++)
					{
						if(i!=1)dp[i+1][l][j] = max(dp[i+1][l][j],dp[i][j][k] + max(s[i][max(k,l)] - s[i][j],zero));
						else dp[i+1][l][j] = max(dp[i+1][l][j],dp[i][j][k] + max(s[i][l] - s[i][j],zero)); 
					}
				}
			}
			if(i!=1)
			{
				for(int j=0;j<=min(N,9);j++)
				{
					for(int k=0;k<=min(N,9);k++)
					{
						for(int pp=0;pp<=min(N,9);pp++)
						{
							dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][pp] + max(s[i][k] - s[i][j],zero));
						}
					}
				}
			}
		}
		for(int i=1;i<=N;i++)
		{
			for(int j=0;j<=min(N,9);j++)
			{
				for(int k=0;k<=min(N,9);k++)
				{
					maxn = max(maxn,dp[i][j][k]);
				}
			}
		}
		return maxn;
	}
	else
	{
		for(int i=0;i<X.size();i++)vv[X[i]].push_back(make_pair(Y[i],W[i]));
		for(int i=0;i<X.size();i++)
		{
			row[X[i]-1].push_back(Y[i]);
			row[X[i]+1].push_back(Y[i]);
		}
		for(int i=1;i<=N;i++)
		{
			row[i].push_back(0);
			sort(row[i].begin(),row[i].end());
			sort(vv[i].begin(),vv[i].end());
		}
		for(int i=1;i<=N;i++)
		{
			for(int j=0;j<row[i].size();j++)
			{
				for(int k=0;k<row[i-1].size();k++)
				{
					for(int l=0;l<row[i+1].size();l++)
					{
						int maxcol = row[i+1][l];
						if(i!=1)maxcol = max(row[i-1][k],maxcol);
						
						int del = find(i,row[i][j]);
						int ad = find(i,maxcol);
						
						dp[i+1][l][j] = max(dp[i+1][l][j],dp[i][j][k] + max(ad-del,0));
					}
				}
			}
			
			if(i!=1)
			{
				for(int j=0;j<row[i].size();j++)
				{
					for(int k=0;k<row[i-1].size();k++)
					{
						for(int p=0;p<row[i-2].size();p++)
						{
							int ad = find(i,row[i-1][k]);
							int del = find(i,row[i][j]);
							dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][p] + max(ad-del,0));
						}
					}
				}
			}
		}
		long long int maxn = -1;
		for(int i=1;i<=N;i++)
		{
			for(int j=0;j<row[i].size();j++)
			{
				for(int k=0;k<row[i-1].size();k++)
				{
					maxn = max(maxn,dp[i][j][k]);
					
				}
			}
		}
		return maxn;
	}
	
	//
	
  return 0;
}

Compilation message (stderr)

fish.cpp: In function 'int find(int, int)':
fish.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<vv[coll].size();i++)
      |              ~^~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0;i<X.size();i++)if(X[i] %2 != 0)flag1 = false;
      |              ~^~~~~~~~~
fish.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i=0;i<W.size();i++)su += W[i];
      |               ~^~~~~~~~~
fish.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0;i<X.size();i++)if(X[i] > 1)flag2 = false;
      |              ~^~~~~~~~~
fish.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<X.size();i++)a[X[i]][Y[i]] = W[i];
      |               ~^~~~~~~~~
fish.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<X.size();i++)X[i] += 1;
      |              ~^~~~~~~~~
fish.cpp:66:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(int i=0;i<Y.size();i++)Y[i] += 1;
      |              ~^~~~~~~~~
fish.cpp:123:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for(int i=0;i<X.size();i++)vv[X[i]].push_back(make_pair(Y[i],W[i]));
      |               ~^~~~~~~~~
fish.cpp:124:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for(int i=0;i<X.size();i++)
      |               ~^~~~~~~~~
fish.cpp:137:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    for(int j=0;j<row[i].size();j++)
      |                ~^~~~~~~~~~~~~~
fish.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int k=0;k<row[i-1].size();k++)
      |                 ~^~~~~~~~~~~~~~~~
fish.cpp:141:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |      for(int l=0;l<row[i+1].size();l++)
      |                  ~^~~~~~~~~~~~~~~~
fish.cpp:156:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int j=0;j<row[i].size();j++)
      |                 ~^~~~~~~~~~~~~~
fish.cpp:158:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |      for(int k=0;k<row[i-1].size();k++)
      |                  ~^~~~~~~~~~~~~~~~
fish.cpp:160:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |       for(int p=0;p<row[i-2].size();p++)
      |                   ~^~~~~~~~~~~~~~~~
fish.cpp:173:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |    for(int j=0;j<row[i].size();j++)
      |                ~^~~~~~~~~~~~~~
fish.cpp:175:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for(int k=0;k<row[i-1].size();k++)
      |                 ~^~~~~~~~~~~~~~~~

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