oj.uz

Submission #631133

# Submission time Handle Problem Language Result Execution time Memory
631133 2022-08-17T17:44:16 Z oliversommer Catfish Farm (IOI22_fish) C++17
6 / 100
 104 ms 24928 KB 
#include "fish.h"

#include <assert.h>

#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

struct Fish {
	int x, y, weight;
	bool operator<(const Fish& a) const {
		return y < a.y;	 // x == a.x ? y < a.y : x < a.x;
	}
};

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	vector<Fish> all_fish(M);
	for (int i = 0; i < M; ++i) {
		all_fish[i] = {X[i], Y[i], W[i]};
	}
	// sort(all_fish.begin(), all_fish.end());

	vector<long long> pref_sum0(N + 1), pref_sum1(N + 1);
	int pivot = 0;
	for (int i = 0; i < M; ++i) {
		Fish& a = all_fish[i];
		assert(a.x == 0 || a.x == 1);
		if (a.x == 0) {
			pref_sum0[a.y + 1] = a.weight;
		} else {
			pref_sum1[a.y + 1] = a.weight;
		}
	}

	// prefix sum
	for (int i = 1; i <= N; ++i) {
		pref_sum0[i] += pref_sum0[i - 1];
		pref_sum1[i] += pref_sum1[i - 1];
	}
	
	if(N == 2) {
		return max(pref_sum0[N], pref_sum1[N]);
	}

	// find pivot
	for (int i = 0; i <= N; ++i) {
		if (pref_sum0[i] + pref_sum1[N] - pref_sum1[i] > pref_sum0[pivot] + pref_sum1[N] - pref_sum1[pivot]) {
			pivot = i;
		}
	}

	return pref_sum0[pivot] + pref_sum1[N] - pref_sum1[pivot];
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4436 KB Output is correct
2 Correct 28 ms 5376 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Runtime error 104 ms 24928 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 63 ms 7444 KB Output is correct
3 Correct 57 ms 8904 KB Output is correct
4 Correct 43 ms 4424 KB Output is correct
5 Correct 28 ms 5304 KB Output is correct
6 Correct 1 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 1 ms 1748 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 24 ms 4584 KB Output is correct
13 Correct 40 ms 5312 KB Output is correct
14 Correct 23 ms 4456 KB Output is correct
15 Correct 28 ms 4940 KB Output is correct
16 Correct 24 ms 4456 KB Output is correct
17 Correct 27 ms 4932 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Runtime error 2 ms 3540 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Runtime error 2 ms 3540 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4436 KB Output is correct
2 Correct 28 ms 5376 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Runtime error 104 ms 24928 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -