Submission #630073

#	Time	Username	Problem	Language	Result	Execution time	Memory
630073		ash7728	Catfish Farm (IOI22_fish)	C++17	3 / 100	1078 ms	56860 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define N 300020
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = (ll)(1e17);

int n, m;
ll pref[N];
vector<vector<int>> fish;
vector<vector<int>> col[N];

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++){
		fish.pb({X[i], Y[i], W[i]});
		col[X[i]].pb({Y[i], W[i], i});
	}
	for(int c = 0;c < n; c++){
		sort(all(col[c]));
		ll acum = 0;
		for(auto x: col[c]) acum += W[x[2]],pref[x[2]]=acum;
	}
	vector<ll> olds = {0,0}, dp(m+1);
	for(int c = 0; c < n; c++){
		ll opt = -INF;
		for(auto x: col[c]){
			dp[x[2]] = min(INF,olds[sz(olds)-2] + pref[x[2]]);		
			
			if(c >= 1 and c < n-1){
				for(auto v: col[c-1]){
					ll cost = 0, cost2=0;

					vector<int> cc = {Y[v[2]],(int)(1e9),(int)(1e9)};
					auto it = upper_bound(all(col[c]), cc);
					if(it != col[c].begin()){
						--it;
						cost = pref[(*it)[2]];
					}

					if(Y[v[2]] <= Y[x[2]]){
						dp[x[2]] = max(dp[x[2]], dp[v[2]] + pref[x[2]] -cost);
					}
				}
			}
			else if(c == 0)dp[x[2]] = pref[x[2]];

			opt=max(opt, dp[x[2]]);
		}
		olds.pb(max(olds.back(), opt));
	}

	return olds.back();
}

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:36:19: warning: unused variable 'cost2' [-Wunused-variable]
   36 |      ll cost = 0, cost2=0;
      |                   ^~~~~

• 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