XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#38812 #1206. Day4D. ZJY 沉迷群星的原因 Accepted 100 136 ms 1796 K C++ 11 / 1.0 K JamesHelium 2020-07-14 23:26:27
显示原始代码 
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <string>

using ll = long long;
const int MaxN(7005), MaxM(200005);

ll m[MaxN], v[MaxN], dp[MaxM];
bool is_inf[MaxN];
int tot(0);

int main() {
    int n, M;
    scanf("%d%d", &n, &M);
    for (int i(0); i < n; ++i) {
        ll mi, vi, ki;
        scanf("%lld%lld%lld", &mi, &vi, &ki);
        if (ki == -1) {
            m[tot] = mi;
            v[tot] = vi;
            is_inf[tot] = true;
            ++tot;
        } else {
            ll ind(1);
            while (ind < ki && ind * mi <= M) {
                ki -= ind;
                m[tot] = mi * ind;
                v[tot] = vi * ind;
                ++tot;
                ind <<= 1;
            }
            if (ki) {
                m[tot] = mi * ki;
                v[tot] = vi * ki;
                ++tot;
            }
        }
    }
    for (int i(0); i < tot; ++i) {
        if (is_inf[i]) {
            for (int j(0); j + m[i] <= M; ++j) {
                dp[j + m[i]] = std::max(dp[j] + v[i], dp[j + m[i]]);
            }
        } else {
            for (int j(M); j - m[i] >= 0; --j) {
                dp[j] = std::max(dp[j - m[i]] + v[i], dp[j]);
            }
        }
    }
    printf("%lld", dp[M]);
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：17 ms
内存：1224 KiB

输入文件（data0.in） 

160 123520
25130 430485880 -1
36496 489918800 -1
98272 697114000 -1
32128 548240028 325708000
2
<3502 bytes omitted>

答案文件（data0.out） 

140828422016

用户输出 

140828422016

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：14 ms
内存：1708 KiB

输入文件（data1.in） 

80 183100
107340 800776768 -1
42988 856483840 -1
38520 902509824 -1
95940 2188800 -1
60452 3049
<1741 bytes omitted>

答案文件（data1.out） 

1046278791360

用户输出 

1046278791360

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：5 ms
内存：516 KiB

输入文件（data2.in） 

162 39520
5320 811768320 -1
4635 11948760 -1
14896 754542166 -1
123656 208101200 -1
28080 58360
<3500 bytes omitted>

答案文件（data2.out） 

138281443200

用户输出 

138281443200

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：2 ms
内存：228 KiB

输入文件（data3.in） 

0 43330

答案文件（data3.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：4 ms
内存：1384 KiB

输入文件（data4.in） 

6 192768
155124 494022800 -1
180090 164598875 -1
190724 718715740 -1
99195 990411000 -1
40704 9
<41 bytes omitted>

答案文件（data4.out） 

3737620000

用户输出 

3737620000

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：19 ms
内存：1688 KiB

输入文件（data5.in） 

140 193184
110448 480826368 -1
76520 482030152 -1
149160 17488073 539725920
124608 68825472 5957
<3107 bytes omitted>

答案文件（data5.out） 

99538065536

用户输出 

99538065536

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：9 ms
内存：1544 KiB

输入文件（data6.in） 

70 176388
118720 235236390 646918500
189140 819871300 -1
45531 21904512 -1
73684 474329800 44709
<1510 bytes omitted>

答案文件（data6.out） 

33889691520

用户输出 

33889691520

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：8 ms
内存：1720 KiB

输入文件（data7.in） 

50 194800
188800 955424800 -1
102000 608691200 688778000
61778 545972900 58892288
65200 39349981
<1021 bytes omitted>

答案文件（data7.out） 

16756062304

用户输出 

16756062304

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：32 ms
内存：1392 KiB

输入文件（data8.in） 

136 158764
114520 648803511 -1
70360 707589524 -1
14224 210781520 -1
42200 33270725 -1
26068 25
<3037 bytes omitted>

答案文件（data8.out） 

128691604800

用户输出 

128691604800

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：6 ms
内存：920 KiB

输入文件（data9.in） 

40 88192
76500 609574400 -1
61920 9135616 -1
28500 297075328 494138744
75480 276408620 109913890
<813 bytes omitted>

答案文件（data9.out） 

14765745280

用户输出 

14765745280

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：18 ms
内存：1796 KiB

输入文件（data10.in） 

55 194800
188800 955424800 -1
102000 608691200 688778000
61778 545972900 58892288
65200 39349981
<1102 bytes omitted>

答案文件（data10.out） 

18311085214

用户输出 

18311085214

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：2 ms
内存：232 KiB

输入文件（data11.in） 

5 50
2 8 5
3 9 -1
10 45 1
12 18 -1
5 19 126

答案文件（data11.out） 

199

用户输出 

199

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.