Submission #829302

#	Time	Username	Problem	Language	Result	Execution time	Memory
829302		FatihSolak	메기 농장 (IOI22_fish)	C++17	3 / 100	159 ms	41816 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
	vector<pair<int,int>> v[N];
	vector<long long>pre[N];
	for(int i = 0;i<M;i++){
		v[X[i]].push_back({Y[i],W[i]});
	}
	for(int i = 0;i<N;i++){
		v[i].push_back({N,0});
		sort(v[i].begin(),v[i].end());
		pre[i].assign(v[i].size(),0);
		for(int j = 0;j<v[i].size();j++){
			pre[i][j] = v[i][j].second + (j?pre[i][j-1]:0);
		}
	}
	vector<pair<int,long long>> tmpsmaller;
	vector<pair<int,long long>> tmpbigger;
	vector<pair<int,long long>> smaller;
	vector<pair<int,long long>> smaller2;
	vector<pair<int,long long>> bigger;
	vector<pair<int,long long>> bigger2;
	tmpsmaller.push_back({-1,0});
	tmpbigger.push_back({-1,0});
	smaller.push_back({-1,0});
	smaller2.push_back({-1,0});
	bigger.push_back({-1,0});
	bigger2.push_back({-1,0});
	for(int i = 0;i<N;i++){
		int sz = v[i].size();
		int prevsz = smaller.size();
		vector<pair<int,long long>> nwsmaller(sz,{0,-1e18});
		vector<pair<int,long long>> nwsmaller2(sz,{0,-1e18});
		vector<pair<int,long long>> nwtmpsmaller(sz,{0,-1e18});
		vector<pair<int,long long>> nwbigger(sz,{0,-1e18});
		vector<pair<int,long long>> nwbigger2(sz,{0,-1e18});
		vector<pair<int,long long>> nwtmpbigger(sz,{0,-1e18});
		vector<pair<int,long long>> smaller3;
		vector<pair<int,long long>> smaller4;
		vector<pair<int,long long>> bigger3;
		vector<pair<int,long long>> bigger4;
		int pt1 = -1;
		for(int j = 0;j<prevsz;j++){
			while(i && pt1 != sz && v[i][pt1+1].first <= v[i-1][j].first-1)
				pt1++;
			smaller3.push_back({tmpsmaller[j].first,tmpsmaller[j].second + (pt1 == -1?0:pre[i][pt1])});
			smaller4.push_back({tmpsmaller[j].first,tmpsmaller[j].second});
			bigger3.push_back({tmpbigger[j].first,tmpbigger[j].second + (pt1 == -1?0:pre[i][pt1])});
			bigger4.push_back({tmpbigger[j].first,tmpbigger[j].second});
		}
		for(int j = prevsz-2;j>=0;j--){
			smaller3[j] = max(smaller3[j],smaller3[j+1]);
			smaller4[j] = max(smaller4[j],smaller4[j+1]);
			bigger3[j] = max(bigger3[j],bigger3[j+1]);
			bigger4[j] = max(bigger4[j],bigger4[j+1]);
		}
		for(int j = 0;j<sz;j++){
			nwsmaller[j].first = v[i][j].first-1;
			nwsmaller2[j].first = v[i][j].first-1;
			nwtmpsmaller[j].first = v[i][j].first-1;
			nwbigger[j].first = v[i][j].first-1;
			nwbigger2[j].first = v[i][j].first-1;
			nwtmpbigger[j].first = v[i][j].first-1;
		}
		pt1 = -1;
		for(int j = 0;j<sz;j++){
			while(pt1 != prevsz - 1 && smaller[pt1 + 1].first < v[i][j].first)
				pt1++;
			if(pt1 != -1){
				nwbigger[j].second = max(nwbigger[j].second,smaller[pt1].second);
				nwbigger[j].second = max(nwbigger[j].second,smaller2[pt1].second + (i?pre[i-1][pt1]:0));
				nwbigger[j].second = max(nwbigger[j].second,bigger2[pt1].second + (i?pre[i-1][pt1]:0));
			}
			nwbigger2[j].second = nwbigger[j].second - (j?pre[i][j-1]:0);
			nwtmpbigger[j] = nwbigger[j];
			if(j){
				nwbigger[j].second = max(nwbigger[j].second,nwbigger[j-1].second);
				nwbigger2[j].second = max(nwbigger2[j].second,nwbigger2[j-1].second);
			}
		}
		pt1 = 0;
		for(int j = 0;j<sz;j++){
			while(pt1 != prevsz && smaller[pt1].first < v[i][j].first)
				pt1++;
			if(pt1 != prevsz){
				nwsmaller[j].second = max(nwsmaller[j].second,smaller3[pt1].second - (j?pre[i][j-1]:0));
				nwsmaller[j].second = max(nwsmaller[j].second,bigger3[pt1].second - (j?pre[i][j-1]:0));
				nwsmaller2[j].second = max(nwsmaller2[j].second,smaller4[pt1].second);
				nwsmaller2[j].second = max(nwsmaller2[j].second,bigger4[pt1].second);
			}
			nwtmpsmaller[j] = nwsmaller[j];
			if(j){
				nwsmaller[j].second = max(nwsmaller[j].second,nwsmaller[j-1].second);
				nwsmaller2[j].second = max(nwsmaller2[j].second,nwsmaller2[j-1].second);
			}
		}
		smaller = nwsmaller;
		smaller2 = nwsmaller2;
		tmpsmaller = nwtmpsmaller;
		bigger = nwbigger;
		bigger2 = nwbigger2;
		tmpbigger = nwtmpbigger;
		// cout << i << endl;
		// for(auto u:tmpsmaller){
		// 	cout << u.first << ' ' << u.second << endl;
		// }
		// cout << endl;
		// for(auto u:tmpbigger){
		// 	cout << u.first << ' ' << u.second << endl;
		// }
		// cout << endl;
	}
	return max(smaller.back().second,bigger.back().second);
}

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:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for(int j = 0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~

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