oj.uz

Submission #635530

# Submission time Handle Problem Language Result Execution time Memory
635530 2022-08-26T11:25:18 Z marvinthang Catfish Farm (IOI22_fish) C++17
9 / 100
 184 ms 38480 KB 
/*************************************
*    author: marvinthang             *
*    created: 26.08.2022 17:36:44    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                 div  ___div
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define             FULL(i)  (MASK(i) - 1)
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class T>             scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T>            print_op(vector <T>)  { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V>   scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V>  print_op(pair <U, V>)  { return out << '(' << u.fi << ", " << u.se << ')'; }
template <class A, class B>   inline bool minimize(A &a, B b)  { A eps = 1e-9; if (a > b + eps) { a = b; return true; } return false; }
template <class A, class B>   inline bool maximize(A &a, B b)  { A eps = 1e-9; if (a + eps < b) { a = b; return true; } return false; }

const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const long long oo = 1e18;

long long max_weights(int numCol, int numCatfish, vector <int> cols, vector <int> rows, vector <int> weights) {
	vector <vector <pair <int, long long>>> atCol(numCol);
	for (int i = 0; i < numCatfish; ++i) 
		atCol[cols[i]].push_back(make_pair(rows[i], weights[i]));
	for (int i = 0; i < numCol; ++i) {
		atCol[i].push_back(make_pair(numCol, 0));
		sort(atCol[i].begin(), atCol[i].end());
		long long pref = 0;
		for (auto &[_, p]: atCol[i]) {
			pref += p;
			p = pref;
		}
	}
	auto prefix_sum = [&] (int i, int x) -> long long {
		assert(0 <= i && i < numCol);
		auto it = lower_bound(atCol[i].begin(), atCol[i].end(), make_pair(x, -1LL));
		if (it != atCol[i].begin()) return prev(it)->se;
		return 0;
	};
	vector <vector <vector <long long>>> F(numCol, vector <vector <long long>> (2));

	for (int i = 0; i < numCol; ++i) {
		F[i][0].assign(atCol[i].size(), 0);
		F[i][1].assign(atCol[i].size(), 0);
		// cout << atCol[i] << '\n';
		if (!i) continue;

		// // down
		long long ma = 0;
		for (int cur = atCol[i].size(), pre = atCol[i - 1].size(); cur--; ) {
			while (pre > 0 && atCol[i - 1][pre - 1].fi >= atCol[i][cur].fi) 
				--pre, maximize(ma, F[i - 1][0][pre] + prefix_sum(i, atCol[i - 1][pre].fi));
			maximize(F[i][0][cur], ma - prefix_sum(i, atCol[i][cur].fi));
			// cout << i << " 0 " << atCol[i][cur].fi - 1 << ' ' << F[i][0][cur] << '\n';
		}

		// // up
		ma = i > 1 ? max(*max_element(F[i - 2][0].begin(), F[i - 2][0].end()), 
						 *max_element(F[i - 2][1].begin(), F[i - 2][1].end())) : 0;
		for (int cur = 0, pre = -1; cur < atCol[i].size(); ++cur) {
			while (pre + 1 < atCol[i - 1].size() && atCol[i - 1][pre + 1].fi <= atCol[i][cur].fi)
				++pre, maximize(ma, F[i - 1][1][pre] - prefix_sum(i - 1, atCol[i - 1][pre].fi));
			maximize(F[i][1][cur], ma + prefix_sum(i - 1, atCol[i][cur].fi));
			// cout << i << " 1 " << atCol[i][cur].fi - 1 << ' ' << F[i][1][cur] << '\n';
		}
	}
	return max(*max_element(F[numCol - 1][0].begin(), F[numCol - 1][0].end()), 
			   *max_element(F[numCol - 1][1].begin(), F[numCol - 1][1].end()));
}

// void process(void) {
// 	int n, m; cin >> n >> m;
// 	vector <int> x(m), y(m), w(m);
// 	cin >> x >> y >> w;
// 	cout << max_weights(n, m, x, y, w) << '\n';
// }

// int main(void) {
// 	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
// 	file("ioi22_day1_fish");
// 	process();
// 	cerr << "Time elapsed: " << TIME << " s.\n";
// 	return (0^0);
// }

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:74:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int cur = 0, pre = -1; cur < atCol[i].size(); ++cur) {
      |                               ~~~~^~~~~~~~~~~~~~~~~
fish.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    while (pre + 1 < atCol[i - 1].size() && atCol[i - 1][pre + 1].fi <= atCol[i][cur].fi)
      |           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 23460 KB Output is correct
2 Correct 75 ms 26532 KB Output is correct
3 Correct 30 ms 20564 KB Output is correct
4 Correct 34 ms 20556 KB Output is correct
5 Correct 178 ms 37540 KB Output is correct
6 Correct 184 ms 38480 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 118 ms 27844 KB Output is correct
3 Correct 129 ms 31908 KB Output is correct
4 Correct 62 ms 23368 KB Output is correct
5 Correct 81 ms 26568 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 30 ms 20576 KB Output is correct
11 Correct 30 ms 20596 KB Output is correct
12 Correct 67 ms 23388 KB Output is correct
13 Correct 76 ms 26456 KB Output is correct
14 Correct 65 ms 23384 KB Output is correct
15 Correct 88 ms 25956 KB Output is correct
16 Correct 68 ms 23436 KB Output is correct
17 Correct 73 ms 25972 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20564 KB Output is correct
2 Correct 32 ms 20572 KB Output is correct
3 Incorrect 54 ms 20968 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '165125946988'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '165125946988'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '165125946988'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20564 KB Output is correct
2 Correct 32 ms 20572 KB Output is correct
3 Incorrect 54 ms 20968 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 23460 KB Output is correct
2 Correct 75 ms 26532 KB Output is correct
3 Correct 30 ms 20564 KB Output is correct
4 Correct 34 ms 20556 KB Output is correct
5 Correct 178 ms 37540 KB Output is correct
6 Correct 184 ms 38480 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 118 ms 27844 KB Output is correct
9 Correct 129 ms 31908 KB Output is correct
10 Correct 62 ms 23368 KB Output is correct
11 Correct 81 ms 26568 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 30 ms 20576 KB Output is correct
17 Correct 30 ms 20596 KB Output is correct
18 Correct 67 ms 23388 KB Output is correct
19 Correct 76 ms 26456 KB Output is correct
20 Correct 65 ms 23384 KB Output is correct
21 Correct 88 ms 25956 KB Output is correct
22 Correct 68 ms 23436 KB Output is correct
23 Correct 73 ms 25972 KB Output is correct
24 Correct 31 ms 20564 KB Output is correct
25 Correct 32 ms 20572 KB Output is correct
26 Incorrect 54 ms 20968 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
27 Halted 0 ms 0 KB -