Submission #1055961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055961		pawned	Catfish Farm (IOI22_fish)	C++17	6 / 100	111 ms	13896 KiB

fish

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "fish.h"

int MAX_R = 10;
int MAX_C = 10;

ll max_weights(int N, int M, vector<int> X_g, vector<int> Y_g, vector<int> W_g) {
	MAX_R = min(N, 3);
	MAX_C = N;
	vector<vi> a(MAX_R, vi(MAX_C, 0));
	for (int i = 0; i < M; i++) {
		if (X_g[i] < MAX_R && Y_g[i] < MAX_C)
			a[X_g[i]][Y_g[i]] += W_g[i];
	}
/*	cout<<"a: "<<endl;
	for (vi v : a) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vi> pfs(MAX_R, vi(MAX_C + 1, 0));	// vertical pfs
	for (int i = 0; i < MAX_R; i++) {
		pfs[i][0] = 0;
		for (int j = 1; j <= MAX_C; j++) {
			pfs[i][j] = pfs[i][j - 1] + a[i][j - 1];
		}
	}
/*	cout<<"pfs: "<<endl;
	for (vi v : pfs) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	if (N == 2) {
		return max(pfs[0][N], pfs[1][N]);
	}
	else {
		ll ans = 0;
		for (int i = 0; i <= N; i++) {
			ans = max(ans, (pfs[0][i] - pfs[0][0]) + (pfs[1][N] - pfs[1][i]));
		}
		return ans;
	}
}

// subtask 2: greedy

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