Submission #763896

#	Time	Username	Problem	Language	Result	Execution time	Memory
763896		OrazB	Catfish Farm (IOI22_fish)	C++17	53 / 100	864 ms	2097152 KiB

fish

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
//Dijkstra->set
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 100005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <ll, ll>
#define pb push_back
#define ff first
#define ss second

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
	bool sub1 = 0, sub2 = 0;
	ll sum = 0, sum1 = 0, sum2 = 0;
	vector<pii> col1, col2;
	for (int i = 0; i < m; i++){
		sub1 |= (x[i]%2);
		sub2 |= (x[i]>1);
		sum += w[i];
		if (!x[i]) col1.pb({y[i], w[i]}), sum1 += w[i];
		else col2.pb({y[i], w[i]}), sum2 += w[i];
	}
	if (!sub1) return sum;
	if (!sub2){
		if (n == 2) return max(sum1, sum2);
		sort(all(col1)); sort(all(col2));
		ll mx = sum2;
		int pos = 0;
		for (auto i : col1){
			while(pos < (int)col2.size() and col2[pos].ff <= i.ff){
				sum2 -= col2[pos].ss;
				pos++;
			}
			sum2 += i.ss;
			mx = max(mx, sum2);
		}
		return mx;
	}
	int nn = *max_element(all(y))+1;
	vector<vector<ll>> a(n+2, vector<ll> (nn+2, 0));
	for (int i = 0; i < m; i++){
		a[x[i]+1][y[i]+1] = w[i];
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= nn; j++){
			a[i][j] += a[i][j-1];
		}
	}
	vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(nn+1, vector<ll>(nn+1, 0)));
	vector<vector<ll>> pref(nn+1, vector<ll>(nn+1, 0)), suff(nn+1, vector<ll>(nn+1, 0));
	ll ans = 0;
	for (int i = 2; i <= n; i++){
		for (int j = 0; j <= nn; j++){
			for (int k = 0; k <= nn; k++){
				if (k <= j){
					dp[i][j][k] = max(pref[k][j]+(a[i-1][j]-a[i-1][k]), suff[k][j]);
				}else{
					dp[i][j][k] = max(dp[i][j][k], suff[k][0]+a[i][k]-a[i][j]);
				}
				if (i == n) ans = max(ans, dp[i][j][k]);
			}
		}
		for (int j = 0; j <= nn; j++){
			pref[j][0] = dp[i][j][0];
			for (int k = 1; k <= nn; k++){
				pref[j][k] = max(pref[j][k-1], dp[i][j][k]-(k>j ? a[i][k]-a[i][j] : 0));
			}
			suff[j][nn] = dp[i][j][nn];
			for (int k = nn-1; k >= 0; k--) suff[j][k] = max(suff[j][k+1], dp[i][j][k]);
		}
	}
	return ans;
}

// int main ()
// {
// 	int n, m;
// 	cin >> n >> m;
// 	vector<int> x(m), y(m), w(m);
// 	for (int i = 0; i < m; i++) cin >> x[i] >> y[i] >> w[i];
// 	cout << max_weights(n,m,x,y,w);
// }	

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