oj.uz

답안 #630999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630999 2022-08-17T12:36:33 Z fadyscube 메기 농장 (IOI22_fish) C++17
0 / 100
 1000 ms 2097152 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

#define ll long long

vector<vector<int>> v = {{-1}};
ll ans = 0;
int prev_index = -1;
int prev_limit = -1;

ll max_weights (int n, int m, vector<int> x, vector<int> y, vector<int> w) {
	vector<vector<int>> v2 = {{-1}};
	if (v == v2) {
		vector<vector<int>> v3(n, vector<int>(n, 0));
		v = v3;
		for (int i = 0; i < m; i++)
			v[x[i]][y[i]] = w[i];
	}
	// base case
	int count = 0;
	for (int i = 0; i < n; i++)
		if (v[i].size() > n) count++;

	// cout << count << endl;
	if (count >= n-1) {
		return ans;
	}

	// output variables
	// ll ans = 0;
	// prosess input


	// get max weight column
	vector<pair<int, int>> mxs(n);
	for (int i = 0; i < n; i++) {
		if (v[i].size() == n)
			mxs[i] = make_pair(accumulate(v[i].begin(), v[i].end(), 0), i);
		else
			mxs[i] = make_pair(-1, -1);
	}

	auto mx_pair = max_element(mxs.begin(), mxs.end());
	auto mx = mx_pair->second; // index
	ll mx_sum = mx_pair->first; // sum
	// assign pier column to the min weight column from the two adjacents ones
	int mn; // index
	if (0 <= mx+1 && mx+1 < n && 0 <= mx-1 && mx-1 < n) {
		mn = min(mxs[mx-1], mxs[mx+1]).second;
		if (mxs[mx-1].second == -1 && mxs[mx+1].second == -1) {
			v[mx].push_back(0);
			prev_index = -1;
			prev_limit = -1;
			return max_weights(n, m, x, y, w);
		} else if (mxs[mx-1].second == -1) {
			mn = mxs[mx+1].second;
		} else if (mxs[mx+1].second == -1) {
			mn = mxs[mx-1].second;
		} else {
			mn = min(mxs[mx+1], mxs[mx-1]).second;
		}
	} else if (0 <= mx+1 && mx+1 < n) {
		if (mxs[mx+1].second == -1) {
			v[mx].push_back(0);
			prev_index = -1;
			prev_limit = -1;
			return max_weights(n, m, x, y, w);
		}
		mn = mxs[mx+1].second;
	} else {
		if (mxs[mx-1].second == -1) {
			v[mx].push_back(0);
			prev_index = -1;
			prev_limit = -1;
			return max_weights(n, m, x, y, w);
		}
		mn = mxs[mx-1].second;
	}

	int other = -1; // index
	int other_sum = 0; // sum
	if (mn-1 == mx && 0 <= mn+1 && mn+1 < n) {
		other_sum = accumulate(v[mn+1].begin(), v[mn+1].end(), 0);
		other = mn+1;
	} else if (mn+1 == mx && 0 <= mn-1 && mn-1 < n) {
		other_sum = accumulate(v[mn-1].begin(), v[mn-1].end(), 0);
		other = mn-1;
	}


	int limit = 0;
	for (int i = n-1; i >= 0; i--) {
		if (other != -1) {
			if (v[mx][i] > 0 || v[other][i] > 0) {
				limit = i+1;
				break;
			}
		} else {
			if (v[mx][i] > 0) {
				limit = i+1;
				break;
			}
		}
	}

	// turn max weight column and pier column into zeros
	if (prev_index == mn && prev_limit != -1 && prev_limit != -1) {
		if (prev_limit <= limit) {
			v[mn].push_back(0);
			return max_weights(n, m, x, y, w);
		}
	}

	ans += mx_sum;
	ans += other_sum;
	fill(v[mn].begin(), v[mn].begin()+limit-1, 0);
	v[mn].push_back(0);
	fill(v[mx].begin(), v[mx].end(), 0);
	if (other != -1) fill(v[other].begin(), v[other].end(), 0);

	// go to the next max column
	return max_weights(n, m, x, y, w);
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:26:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   if (v[i].size() > n) count++;
      |       ~~~~~~~~~~~~^~~
fish.cpp:41:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |   if (v[i].size() == n)
      |       ~~~~~~~~~~~~^~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1073 ms 2097152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 832 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 779 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 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 0 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 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 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 0 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 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 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 0 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 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 779 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1073 ms 2097152 KB Time limit exceeded
2 Halted 0 ms 0 KB -