oj.uz

Submission #626852

# Submission time Handle Problem Language Result Execution time Memory
626852 2022-08-11T21:42:13 Z Noam527 Catfish Farm (IOI22_fish) C++17
0 / 100
 109 ms 23912 KB 
#include "fish.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 100005;
vector<pair<int, int>> Y[N];
int c[N];
vector<ll> D[N], F[N];
ll E[N];

ll max_weights(int n, int m, vector<int> x, vector<int> y,
                      vector<int> w) {
	for (int i = 0; i < m; i++)
		Y[x[i]].emplace_back(y[i], w[i]);
	for (int i = 0; i < n; i++)
		sort(Y[i].begin(), Y[i].end()), c[i] = Y[i].size();

	// initialize column 0:
	E[0] = 0;
	F[0].resize(c[0], -(ll)1e18);
	D[0].resize(c[0]);
	if (c[0]) {
		D[0][0] = Y[0][0].second;
		for (int j = 1; j < c[0]; j++) {
			D[0][j] = D[0][j - 1] + Y[0][j].second;
		}
	}
	// begin dp:
	for (int i = 1; i < n; i++) {
		E[i] = E[i - 1];
		for (int j = 0; j < c[i - 1]; j++)
			E[i] = max(max(E[i], D[i - 1][j]), F[i - 1][j]);
		if (!c[i]) continue;

		D[i].resize(c[i]);
		F[i].resize(c[i]);

		vector<ll> below(c[i]), above(c[i]);
		// compute below
		int z = 0;
		ll bestfound = -(ll)1e18;
		for (int k = 0; k < c[i]; k++) {
			while (z < c[i - 1] && Y[i - 1][z].first < Y[i][k].first) {
				bestfound = max(bestfound, D[i - 1][z]);
				z++;
			}
			below[k] = bestfound;
		}
		// compute above
		z = c[i - 1] - 1;
		bestfound = -(ll)1e18;
		for (int k = c[i] - 1; k >= 0; k--) {
			while (z >= 0 && Y[i - 1][z].first > Y[i][k].first) {
				bestfound = max(bestfound, F[i - 1][z]);
				z--;
			}
			above[k] = bestfound;
		}
		// compute D:
		ll bestF = -(ll)1e18;
		if (c[i - 1])
			ll bestF = *max_element(F[i - 1].begin(), F[i - 1].end());
		D[i][0] = max(max(below[0], E[i - 1]), bestF) + Y[i][0].second;
		for (int j = 1; j < c[i]; j++) {
			D[i][j] = max(below[j], D[i][j - 1]) + w[j];
		}
		// compute F:
		F[i][c[i] - 1] = max(E[i - 1], above[c[i] - 1]) + Y[i][c[i] - 1].second;
		for (int j = c[i] - 2; j >= 0; j--) {
			F[i][j] = max(above[j], F[i][j - 1]) + w[j];
		}
	}
	ll result = E[n - 1];
	for (int j = 0; j < c[n - 1]; j++) {
		result = max(result, F[n - 1][j]);
	}
	return result;
}

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:63:7: warning: unused variable 'bestF' [-Wunused-variable]
   63 |    ll bestF = *max_element(F[i - 1].begin(), F[i - 1].end());
      |       ^~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12260 KB Output is correct
2 Correct 41 ms 13244 KB Output is correct
3 Correct 5 ms 8404 KB Output is correct
4 Correct 4 ms 8440 KB Output is correct
5 Incorrect 109 ms 23912 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '150089127562057'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Incorrect 63 ms 16720 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40487783832585'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8404 KB Output is correct
2 Correct 4 ms 8404 KB Output is correct
3 Incorrect 34 ms 14612 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8404 KB Output is correct
2 Correct 4 ms 8404 KB Output is correct
3 Incorrect 34 ms 14612 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12260 KB Output is correct
2 Correct 41 ms 13244 KB Output is correct
3 Correct 5 ms 8404 KB Output is correct
4 Correct 4 ms 8440 KB Output is correct
5 Incorrect 109 ms 23912 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '150089127562057'
6 Halted 0 ms 0 KB -