oj.uz

Submission #697718

# Submission time Handle Problem Language Result Execution time Memory
697718 2023-02-10T22:11:31 Z hadi Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 19180 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <array>
#include <assert.h>

using namespace std;

class NoOutput : public std::basic_ostream<char> {

};

template<class V>
NoOutput& operator<<(NoOutput& os, const V& v) {
	return os;
}
NoOutput err;
// ostream& err = cerr;

typedef long long int64 ;
const int64 INF = 1e15L;
const int MAXN = 100000+10;

bool is_sorted(const vector<int>& v) {
	for (size_t i=1; i<v.size(); i++) {
		if (v[i-1] > v[i]) return false;
	}
	return true;
}

// return first index i such that k<=v[i], if not returns v.size()
int lowest_geq(const vector<int>& v, int k) {
	auto it = lower_bound(v.begin(), v.end(), k);
	return it == v.end() ? (int) v.size() : it - v.begin();
}

vector<pair<int,int>> transform_container(const vector<int>& c, std::function<pair<int,int> (int)> &&f)
{
    vector<pair<int,int>> ret;
    std::transform(std::begin(c), std::end(c), std::inserter(ret, std::end(ret)), f);
    return ret;
}

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os << "[";
	for (auto const& vv: v) 
		os << vv << " ";
	return os << "]";
}

struct IntervalTree {
	int n;
	vector<int64> t; 
	vector<int> key;

	void build(const vector<pair<int,int>> key_value) {
		n = key_value.size();
		t.resize(2*n);
		key.clear();
		for (size_t i=0; i<key_value.size(); i++) {
			key.push_back(key_value[i].first);
			t[n+i] = key_value[i].second;
		}
		assert(is_sorted(key));
		for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
	}

	int get_index(int p) const {
		return t[p+n];
	}

	void set_index(int p, int value) {
		for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
	}

	int64 query_index(int l, int r) const {  // sum on interval [l, r)
		int64 res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l&1) res += t[l++];
			if (r&1) res += t[--r];
		}
		return res;
	}

	int lowest_geq_index(int v) const {
		return lowest_geq(key, v);
	}

	int64 query(int l_v, int r_v) const {
		return query_index(lowest_geq(key, l_v), lowest_geq(key, r_v));
	}

};


// sum of weight of fishes in column i in rows [x-y)
int64 fish(const IntervalTree & tree, int x, int y) {
	return tree.query(x, y);
}

int N;
map<int, int64> dp_iminus1_down, dp_i_down, dp_iminus1_up, dp_i_up;

// max_{N>=y >= x} DP[i-1,y,down] + fish(i,[x-y)), DP[i-1,y,up] + fish(i,[x-y))
int64 max_1(const IntervalTree& tree_i, int x) {
	//naive
	int64 res = 0;
	for (int y = x; y <= N; y++) {
		err << "max_1(" << x << ") " << (dp_iminus1_down.find(y) != dp_iminus1_down.end() ? dp_iminus1_down[y] : -INF) << " " << (dp_iminus1_up.find(y) != dp_iminus1_up.end() ? dp_iminus1_up[y] : -INF) << " " << fish(tree_i, x, y) << endl;
		res = max(res, max(
			dp_iminus1_down.find(y) != dp_iminus1_down.end() ? dp_iminus1_down[y] : -INF, 
			dp_iminus1_up.find(y) != dp_iminus1_up.end() ? dp_iminus1_up[y] : -INF) + fish(tree_i, x, y));
	}
	return res;
}

// max_{0<=y<= x} DP[i-1,y,up] + fish(i-1,[y-x))
int64 max_2(const IntervalTree& tree_iminus1, int x) {
	//naive
	int64 res = 0;
	for (int y = 0; y <= x; y++) {
		err << "max_2(" << x << ") " << (dp_iminus1_up.find(y) != dp_iminus1_up.end() ? dp_iminus1_up[y] : -INF) << " " << fish(tree_iminus1, y, x) << endl;
		res = max(res, 
			(dp_iminus1_up.find(y) != dp_iminus1_up.end() ? dp_iminus1_up[y] : -INF) + fish(tree_iminus1, y, x));
	}
	return res;
}

int64 max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	::N = N;
	err << "Input: X=" << X << " Y=" << Y << " W=" << W << endl;

	array<vector<int>, MAXN> column_fish_index;
	for (size_t f=0; f<(size_t)M; f++) {
		column_fish_index[X[f]].push_back(f);
	}

	for (size_t i=0; i<(size_t)N+1; i++) {
		sort(column_fish_index[i].begin(), column_fish_index[i].end(), [&](int f1, int f2) { return Y[f1] < Y[f2]; });
		err << "column_fish_index[" << i << "]=" << column_fish_index[i] << endl;
	}

	IntervalTree tree_iminus1;
	tree_iminus1.build(transform_container(column_fish_index[0], [&Y, &W](int f) { return make_pair(Y[f], W[f]); }));

	dp_iminus1_down = dp_iminus1_up = map<int, int64>();
	dp_iminus1_down[0] = dp_iminus1_up[0] = 0;
	for (size_t c=0; c<=1; c++) {
		for (auto f : column_fish_index[c]) {
			dp_iminus1_up[Y[f]+1] = 0;
		}
	}

	for (size_t i=1; i<(size_t)N+1; i++) {
		err << "Column " << i << endl;
		vector<int> important_rows_i;
		important_rows_i.push_back(0);
		for (size_t c=i-1; c<=i+1; c++) {
			for (auto f : column_fish_index[c]) {
				important_rows_i.push_back(Y[f]+1);
			}
		}
		sort(important_rows_i.begin(), important_rows_i.end());
		//err << "important_rows_i: " << important_rows_i << endl;
		important_rows_i.resize(unique(important_rows_i.begin(), important_rows_i.end()) - important_rows_i.begin());
		err << "important_rows_i: " << important_rows_i << endl;
		
		//fill fish interval tree
		IntervalTree tree_i;
		tree_i.build(transform_container(column_fish_index[i], [&Y, &W](int f) { return make_pair(Y[f], W[f]); }));

		dp_i_down = dp_i_up = map<int, int64>();
		for (auto x : important_rows_i) {
			dp_i_down[x] = max_1(tree_i, x);
			dp_i_up[x] = max(max_2(tree_iminus1, x), dp_iminus1_down[0]);
			err << "dp[" << i << "," << x << "]=" << dp_i_down[x] << " ^:" << dp_i_up[x] << endl;
		}
		dp_iminus1_down = dp_i_down;
		dp_iminus1_up = dp_i_up;

		tree_iminus1 = tree_i;
	}
	return dp_iminus1_down[0];
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 13640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 1054 ms 19180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2600 KB Output is correct
4 Correct 2 ms 2608 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2612 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2600 KB Output is correct
9 Correct 7 ms 2676 KB Output is correct
10 Correct 43 ms 2740 KB Output is correct
11 Correct 12 ms 2644 KB Output is correct
12 Correct 36 ms 2688 KB Output is correct
13 Correct 3 ms 2644 KB Output is correct
14 Correct 25 ms 2620 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2600 KB Output is correct
4 Correct 2 ms 2608 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2612 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2600 KB Output is correct
9 Correct 7 ms 2676 KB Output is correct
10 Correct 43 ms 2740 KB Output is correct
11 Correct 12 ms 2644 KB Output is correct
12 Correct 36 ms 2688 KB Output is correct
13 Correct 3 ms 2644 KB Output is correct
14 Correct 25 ms 2620 KB Output is correct
15 Correct 14 ms 2644 KB Output is correct
16 Correct 43 ms 2772 KB Output is correct
17 Execution timed out 1082 ms 4684 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2600 KB Output is correct
4 Correct 2 ms 2608 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2612 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2600 KB Output is correct
9 Correct 7 ms 2676 KB Output is correct
10 Correct 43 ms 2740 KB Output is correct
11 Correct 12 ms 2644 KB Output is correct
12 Correct 36 ms 2688 KB Output is correct
13 Correct 3 ms 2644 KB Output is correct
14 Correct 25 ms 2620 KB Output is correct
15 Correct 14 ms 2644 KB Output is correct
16 Correct 43 ms 2772 KB Output is correct
17 Execution timed out 1082 ms 4684 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 13640 KB Time limit exceeded
2 Halted 0 ms 0 KB -