글 읽기 - 반례가필요합니다

imscs22 3년 전 1

채점기 돌려보니 틀렸습니다가 뜹니다

어떤 반례가 있는 것일까요?

//...생략
typedef pair<int,int> Data;
#define w first
#define v second
int n,k;
int main(){
    cin>>n>>k;
    vector<Data> items;
    items.reserve(n);
    int dp[100002]={0,};
    int offset = 2e30;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        items.push_back(make_pair(a,b));
        offset = min(offset,a);
    }
    int maxv =0 ;
    for(int i=offset;i<=k;i++){
        for(int j=0;j<items.size();j++){
            const int W = items[j].w;
            const int V = items[j].v;
            if(i-W>=0){
                dp[i]=max(max(dp[i],dp[i-1]),max(dp[i-W],dp[i-W]+V));
                if(V>0&&i%W==0)dp[i]=max(dp[i],(i/W)*V);
            }
        }
        maxv = max(maxv,dp[i]);
    }
    cout<<maxv<<endl;
    return 0;
}

jh05013 3년 전 1

물건은 하나씩만 있습니다.

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

문제

문제

출처

ICPC

반례가필요합니다

imscs22 3년 전 1

jh05013 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말