Submission #626303

#	Time	Username	Problem	Language	Result	Execution time	Memory
626303		Antekb	Catfish Farm (IOI22_fish)	C++17	9 / 100	156 ms	32304 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define pb push_back
#define st first
#define nd second
using namespace std;
using ll = long long;
const int INF=1e9+5;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
	/*n=1e5;
	m=1e5;
	X.resize(m);
	Y.resize(m);
	W.resize(m);
	for(int i=0; i<m; i++){
		X[i]=(rng()%(n/2))*2+2;
		Y[i]=rng()%n;
		W[i]=rng();
	}*/
	for(auto &i:X)i++;
	ll ans=0;
	for(int i:W)ans+=i;
	//return ans;
	vector<pair<int, int> > V[n+2];	
	vector<ll> dp[n+2][2];
	ll dp2[n+2][2];
	for(int i=0; i<=n+1; i++)dp2[i][0]=dp2[i][1]=0;
	for(int i=0; i<m; i++){
		V[X[i]].pb({Y[i], W[i]});
	}
	for(int i=0; i<=n+1; i++){
		V[i].pb({n, INF});
		sort(V[i].begin(), V[i].end());
		dp[i][0].resize(V[i].size());
		dp[i][1].resize(V[i].size());
	}
	dp[0][1][0]=dp[0][0][0]=-1e18;
	for(int i=1; i<=n+1; i++){
		ll s=0;
		int wsk=0;
		for(int j=0; j<V[i-1].size(); j++){
			dp[i-1][0][j]-=s;
			s+=V[i-1][j].nd;
		}
		ll m=dp2[i-1][0];
		dp2[i][0]=max(dp2[i-1][0], dp2[i-1][1]);
		s=0;
		for(int j=0; j<V[i].size(); j++){
			while(wsk<V[i-1].size() && V[i][j].st>V[i-1][wsk].st){
				m=max(m, dp[i-1][0][wsk]);
				s+=V[i-1][wsk].nd;
				wsk++;
			}
			dp[i][0][j]=s+m;
		}
		wsk=V[i-1].size()-1;
		m=dp[i-1][1][wsk];
		for(int j=V[i].size()-2; j>=0; j--){
			while(wsk!=0 && V[i-1][wsk-1].st>V[i][j].st){
				m=max(m, dp[i-1][1][wsk-1]);
				wsk--;
			}
			dp[i][1][j]=m;
			m+=V[i][j].nd;
		}
		for(int j=0; j<V[i-1].size(); j++)dp2[i][0]=max(dp2[i][0], dp[i-1][1][j]);
		dp2[i][1]=max(m, dp2[i][0]);
		for(int j=0; j<V[i].size(); j++){
			dp[i][0][j]=max(dp[i][0][j], dp2[i-1][1]);
		}
		for(int j=0; j<V[i].size(); j++){
			dp[i][1][j]=max(dp[i][0][j], dp[i][1][j]);
		}
		//cout<<i<<"\n";
		//cout<<dp2[i][0]<<" "<<dp2[i][1]<<" a\n";
		for(int j=0; j<V[i].size(); j++){
			//cout<<dp[i][0][j]<<" "<<dp[i][1][j]<<" b\n";
		}
	}
	//assert(dp2[n+1][0]==ans);
	return dp2[n+1][0];
}

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int j=0; j<V[i-1].size(); j++){
      |                ~^~~~~~~~~~~~~~
fish.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~
fish.cpp:50:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    while(wsk<V[i-1].size() && V[i][j].st>V[i-1][wsk].st){
      |          ~~~^~~~~~~~~~~~~~
fish.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int j=0; j<V[i-1].size(); j++)dp2[i][0]=max(dp2[i][0], dp[i-1][1][j]);
      |                ~^~~~~~~~~~~~~~
fish.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~
fish.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~
fish.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 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