Submission #625929

#	Time	Username	Problem	Language	Result	Execution time	Memory
625929		haojiandan	Catfish Farm (IOI22_fish)	C++17	100 / 100	323 ms	52964 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
typedef long long ll;
const int maxn=(1e5)+10;
int n,m;
vector<pair<int,int> > vec[maxn];
vector<int> pos[maxn];
vector<ll> dp[maxn][2];
vector<ll> sum[maxn];
ll S(int i,int j) {
	j=lower_bound(vec[i].begin(),vec[i].end(),MP(j+1,0))-vec[i].begin()-1;
	if (j<0) return 0;
	return sum[i][j];
}
const ll INF=1e18;
void chkmax(ll &x,ll y) { if (x<y) x=y; }
ll max_weights(int _n,int _m,vector<int> X,vector<int> Y,vector<int> W) {
	n=_n,m=_m;
	for (int i=0;i<m;i++) Y[i]++,vec[X[i]].push_back(MP(Y[i],W[i]));
	for (int i=0;i<n;i++) {
		sort(vec[i].begin(),vec[i].end());
		ll pre=0; pos[i].push_back(0);
		for (int j=0;j<vec[i].size();j++) {
			pre+=vec[i][j].second;
			sum[i].push_back(pre);
			int p=vec[i][j].first;
			if (i>0) pos[i-1].push_back(p);
			pos[i].push_back(p-1);
			if (i<n-1) pos[i+1].push_back(p);
		}
	}
	for (int i=0;i<n;i++) {
		sort(pos[i].begin(),pos[i].end());
		pos[i].resize(unique(pos[i].begin(),pos[i].end())-pos[i].begin());
		//for (int &x : pos[i]) printf("%d %d\n",i,x);
		dp[i][0].resize(pos[i].size());
		dp[i][1].resize(pos[i].size());
		if (i==0) continue;
		ll m0=-INF,m1=-INF,m3=-INF,m4=-INF;
		for (int j=0;j<pos[i-1].size();j++) {
			chkmax(dp[i-1][1][j],dp[i-1][0][j]);
			
			chkmax(m0,dp[i-1][0][j]-S(i-1,pos[i-1][j]));
		//	if (i==1) printf("%d %lld\n",pos[i-1][j],S(i-1,pos[i-1][j]));
			chkmax(m1,dp[i-1][1][j]);
			ll tmp=S(i,pos[i-1][j]);
			chkmax(m3,dp[i-1][1][j]+tmp);
			chkmax(m4,dp[i-1][0][j]-S(i-1,pos[i-1][j])+tmp);
		}
		for (int j=0;j<pos[i].size();j++) {
			chkmax(dp[i][0][j],max(m0+S(i-1,pos[i][j]),m1));
			chkmax(dp[i][1][j],max(m3,m4+S(i-1,pos[i][j]))-S(i,pos[i][j]));
		//	printf("i=%d,pos=%d,dp=%lld %lld\n",i,pos[i][j],dp[i][0][j],dp[i][1][j]);
		}
	}
	ll ans=0;
	for (ll &j : dp[n-1][0]) chkmax(ans,j);
	for (ll &j : dp[n-1][1]) chkmax(ans,j);
	return ans;
}

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:25: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]
   25 |   for (int j=0;j<vec[i].size();j++) {
      |                ~^~~~~~~~~~~~~~
fish.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int j=0;j<pos[i-1].size();j++) {
      |                ~^~~~~~~~~~~~~~~~
fish.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int j=0;j<pos[i].size();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