글 읽기 - cpp 반례 질문

sharon77770 2년 전 0

2%즈음에서 계속 틀렸다고 나옵니다

#include <iostream>
#include <vector>
#include <climits>
#include <cstring>

using namespace std;
using Obj = pair<int, int>; //무게, 값

int dp[101];

inline Obj addAll(const vector<int>& arr, const vector<Obj>& list) {
	Obj r(0, 0);

	for (const int& i : arr) {
		r.first += list[i].first;
		r.second += list[i].second;
	}

	return r;
}

int getMax(vector<int>& arr, const vector<Obj> list, int currIdx, const int& maxW) {
	Obj currObj = addAll(arr, list);

	if (currIdx >= list.size())
		return dp[arr.back()] = currObj.second;

	int MAX = currObj.second;

	for (int i = currIdx; i < list.size(); ++i) {
		if (currObj.first + list[i].first > maxW)
			continue;

		if (dp[i] == -1) {
			arr.push_back(i);
			dp[i] = getMax(arr, list, i + 1, maxW);
			arr.pop_back();
		}

		MAX = max(MAX, dp[i]);
	}

	return MAX;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, K;
	vector<Obj> list;
	vector<int> tmp;

	cin >> N >> K;
	list.resize(N);
	memset(dp, -1, sizeof(dp));

	for (auto& obj : list)
		cin >> obj.first >> obj.second;

	cout << getMax(tmp, list, 0, K);

	return 0;
}

seolminsik 2년 전 0

https://www.acmicpc.net/board/...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

cpp 반례 질문

sharon77770 2년 전 0

seolminsik 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말