#759110 (C++14) No.1858 Gorgeous Knapsack

• 問題: No.1858 Gorgeous Knapsack
• ユーザー: ramia777
• 提出日時: 2022-05-07 16:46:20
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 97 ms / 2,000 ms
• コード長: 2,691 bytes
• コンパイル時間: 939 ms
• コンパイル使用メモリ: 93,372 KB
• 実行使用メモリ: 199,168 KB
• 最終ジャッジ日時: 2024-07-06 22:05:13
• 合計ジャッジ時間: 3,125 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 37

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
//
// Yukicoder
// No.1858
// 
//#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>//list
#include <set> //tree
#include <map> //連想配列
#include <unordered_set> //hash
#include <unordered_map> //hash
#include <algorithm>
#include <iomanip>
#include <string>
#include <stdlib.h>
using namespace std;
typedef unsigned long long ULL;
typedef signed long long SLL;
typedef unsigned int UINT;
#define START (0)
#define RIGHT (1)
#define UP    (2)
#define LEFT  (3)
#define DOWN  (4)
#define DATA_MAX (1000000)
#define FMAX(a,b)  ((a)>(b)?(a):(b))
#define FMIN(a,b)  ((a)<(b)?(a):(b))
//vectorは便利だが処理時間がかかるので注意
vector <vector <SLL>> memo2;//二次元可変配列
vector<SLL> memo1;
SLL H ,A, B, T, F, N, M, Result;
SLL backet[1000005];
SLL dp[5005][5005];
struct BOX {
    SLL w;
    SLL v;
};
BOX box[5005];
//美しさの降順にソート
int compare(const BOX * a, const BOX *b)
{
    if (a->v < b->v)
        return (1);
    else if (a->v > b->v)
        return (-1);
    return (0);
}
int main(int argc, char *argv[])
{
    ULL ans = 0;
    // 入力部
    cin >> N;
    cin >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> box[i].v;
        cin >> box[i].w;
    }
    //Sorting
    qsort(&box[0], N, sizeof(BOX), (int(*)(const void*,const void*))compare);
    //ソート結果のデバッグ出力
    /*
    for (int i = 0; i < N; i++)
    {
        cout << "V=" << box[i].v << ",W=" << box[i].w << endl;
    }*/
    
    //最初の1行目(i=0)
    for (int j = 0; j <= M; j++)
    {
        if (j >= box[0].w)
        {
            dp[0][j] = box[0].v;
            ans = FMAX(ans, box[0].v * dp[0][j]);
        }
    }
    
    //美しさの降順になっているため、i番目以下で最も美しさの小さいものはi番目である
    for(int i=1;i<N;i++)
        for (int j = 0; j <= M; j++)//ナップサックの容量を1つづつ増やしていく
        {
            if (j >= box[i].w)
            {
                    // "j" の容量のときに、下記AとBを比較する
                    // 　　 A: 今回の宝石を入れた場合の価値  → dp[i - 1][j - box[i].w] + box[i].v
                    //  　　B: 今回の宝石を入れなかった場合の価値 → dp[i - 1][j]
                
                if (dp[i - 1][j - box[i].w] + box[i].v > dp[i - 1][j])
                {
                    dp[i][j] = dp[i - 1][j - box[i].w] + box[i].v;
                    ans = FMAX(ans, box[i].v * dp[i][j]);
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
                    
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    
    cout << ans << endl;
    /*
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= M; j++)//ナップサックの容量を1つづつ増やしていく
        {
            cout << dp[i][j] << ",";
        }
        cout << endl;
    }
    */
    ///////////////////
    //cout << endl;
    getchar();
    return 0; //end
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX