글 읽기 - [C++]반례를 찾고 싶습니다

miximum 2년 전 0

게시판에서 나온 반례로는 안되는게 없었는데

10% 도 못가고 틀려버렸네요 ㅠㅜ

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#include <utility>
#include <algorithm>

using namespace std;

//무게 최대 값 DP table
int high[10000001];
vector <pair<int,int>> bag;

struct T
{
    int weight_sum;
    int value_sum;
    int index;
};
//무게 합 오름차순 이후 가치 합 내림차순 정렬
struct Qcompare{
    bool operator()(const T& t1, const T& t2){
        
        if(t1.weight_sum == t2.weight_sum)
            return t1.value_sum > t2.value_sum;
        else
            t1.weight_sum < t2.weight_sum;
    }
};
//무게 오름차순 이후 가치 내림차순 정렬
bool Vcompare(pair<int,int> &a, pair<int,int> &b){
    if(a.first == b.first)
        return a.second > b.second;
    else
        return a.first < b.first;
}

int inBag(int n, int wMax)
{
    priority_queue <T, vector<T>, Qcompare> q;
    int ret = 0;
    
    for(int i=0; i<n; i++)
    {
        q.push({bag[i].first, bag[i].second, i});
        
        while(!q.empty())
        {
            int w_sum = q.top().weight_sum;
            int v_sum = q.top().value_sum;
            int b_idx = q.top().index;
            q.pop();
            
            if(high[w_sum] > v_sum)
                continue;
            //b_idx 이후 부터 검사
            for(int j=b_idx+1; j<n; j++){
                int bag_w = bag[j].first;
                int bag_v = bag[j].second;
                
                if(bag_w+w_sum > wMax)
                    break;
                if(high[bag_w+w_sum] < bag_v+v_sum){
                    q.push({bag_w+w_sum, bag_v+v_sum, j});
                    high[bag_w+w_sum] = bag_v+v_sum;
                }
            }
        }
    }
    
    for(int i=0; i<=wMax; i++){
        if(high[i] > ret)
            ret = high[i];
    }
    return ret;
}

int main()
{
    memset(high, 0, sizeof(high));
    
    int N, K;
    
    cin >> N >> K;
    
    for(int i=0; i<N; i++){
        int W, V;
        cin >> W >> V;
        bag.push_back({W, V});
    }
    
    sort(bag.begin(), bag.end(), Vcompare);
    
    cout << inBag(N, K) << "\n";

    return 0;
}

wnsduds1 2년 전 1

10 999

46 306

60 311

33 724

18 342

57 431

49 288

12 686

89 389

82 889

16 289

ans 4655

+27줄에 return 빼먹으셨어요!

miximum 2년 전 0

return 확인 정말 감사합니다.

그래도 아직 틀렸습니다가 뜨긴해서 좀더 고민해보겠습니다

정말 감사합니다~

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

문제

문제

출처

ICPC

[C++]반례를 찾고 싶습니다

miximum 2년 전 0

wnsduds1 2년 전 1

miximum 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말