{"id":31,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-08-13\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-08-13","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-08-13\/","title":{"rendered":"2020-08-13"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?id=16535<\/a><\/p>\n

<\/a>\u9898\u76ee<\/h5>\n

16535: Lead of Wisdom<\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n

In an online game, \u201cLead of Wisdom\u201d is a place where the lucky player can randomly get powerful items.
\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n

There are k types of items, a player can wear at most one item for each type. For the i-th item, it has four attributes ai,bi,ci and di. Assume the set of items that the player wearing is S, the damage rate of the player DMG can be calculated by the formula:
\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n

Little Q has got n items from \u201cLead of Wisdom\u201d, please write a program to help him select which items to wear such that the value of DMG is maximized.<\/p>\n

<\/a>\u8f93\u5165<\/h5>\n

The first line of the input contains a single integer T (1\u2264T\u226410), the number of test cases.<\/p>\n

For each case, the first line of the input contains two integers n and k (1\u2264n,k\u226450), denoting the number of items and the number of item types.<\/p>\n

Each of the following n lines contains five integers ti,ai,bi,ci and di (1\u2264ti\u2264k, 0\u2264ai,bi,ci,di\u2264100), denoting an item of type ti whose attributes are ai,bi,ci and di.<\/p>\n

<\/a>\u8f93\u51fa<\/h5>\n

For each test case, output a single line containing an integer, the maximum value of DMG.<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
1\n6 4\n1 17 25 10 0\n2 0 0 25 14\n4 17 0 21 0\n1 5 22 0 10\n2 0 16 20 0\n4 37 0 0 0\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
297882000\n<\/code><\/pre>\n
\u66b4\u529b\u641c\u7d22\u5373\u53ef<\/p>\n
#pragma<\/span> GCC optimize(1)<\/span>\n#pragma<\/span> GCC optimize(2)<\/span>\n#pragma<\/span> GCC optimize(3,\"Ofast\",\"inline\")<\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nstruct<\/span> node\n{<\/span>\n    int<\/span> a,<\/span>b,<\/span>c,<\/span>d;<\/span>\n}<\/span>;<\/span>\nvector<<\/span>node><\/span>w[<\/span>60<\/span>]<\/span>;<\/span>\nint<\/span> t,<\/span>n,<\/span>k,<\/span>a,<\/span>b,<\/span>c,<\/span>d,<\/span>e;<\/span>\nint<\/span> cnt=<\/span>0<\/span>;<\/span>\nll max1=<\/span>0<\/span>;<\/span>\nmap<<\/span>int<\/span>,<\/span>int<\/span>><\/span>mp;<\/span>\ninline<\/span> int<\/span> q<\/span>(<\/span>register<\/span> int<\/span> p,<\/span>register<\/span> int<\/span> sum1,<\/span>register<\/span> int<\/span> sum2,<\/span>register<\/span> int<\/span> sum3,<\/span>register<\/span> int<\/span> sum4)<\/span>\n{<\/span>\n    if<\/span>(<\/span>p==<\/span>cnt+<\/span>1<\/span>)<\/span>\n    {<\/span>\n        max1=<\/span>max<\/span>(<\/span>max1,<\/span>(<\/span>ll)<\/span>sum1*<\/span>sum2*<\/span>sum3*<\/span>sum4)<\/span>;<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    }<\/span>\n    if<\/span>(<\/span>w[<\/span>p]<\/span>.<\/span>empty<\/span>(<\/span>)<\/span>)<\/span>\n        q<\/span>(<\/span>p+<\/span>1<\/span>,<\/span>sum1,<\/span>sum2,<\/span>sum3,<\/span>sum4)<\/span>;<\/span>\n    else<\/span>\n        for<\/span>(<\/span>register<\/span> int<\/span> i=<\/span>0<\/span>;<\/span> i<<\/span>w[<\/span>p]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            q<\/span>(<\/span>p+<\/span>1<\/span>,<\/span>sum1+<\/span>w[<\/span>p]<\/span>[<\/span>i]<\/span>.<\/span>a,<\/span>sum2+<\/span>w[<\/span>p]<\/span>[<\/span>i]<\/span>.<\/span>b,<\/span>sum3+<\/span>w[<\/span>p]<\/span>[<\/span>i]<\/span>.<\/span>c,<\/span>sum4+<\/span>w[<\/span>p]<\/span>[<\/span>i]<\/span>.<\/span>d)<\/span>;<\/span>\n        }<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>t)<\/span>;<\/span>\n    while<\/span>(<\/span>t--<\/span>)<\/span>\n    {<\/span>\n        max1=<\/span>0<\/span>;<\/span>\n        scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>k)<\/span>;<\/span>\n        for<\/span>(<\/span>register<\/span> int<\/span> i=<\/span>1<\/span>;<\/span> i<=<\/span>k;<\/span> i++<\/span>)<\/span>\n            w[<\/span>i]<\/span>.<\/span>clear<\/span>(<\/span>)<\/span>;<\/span>\n        mp.<\/span>clear<\/span>(<\/span>)<\/span>;<\/span>\n        cnt=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>register<\/span> int<\/span> i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            scanf<\/span>(<\/span>\"%d%d%d%d%d\"<\/span>,<\/span>&<\/span>e,<\/span>&<\/span>a,<\/span>&<\/span>b,<\/span>&<\/span>c,<\/span>&<\/span>d)<\/span>;<\/span>\n            if<\/span>(<\/span>mp[<\/span>e]<\/span>==<\/span>0<\/span>)<\/span>\n            {<\/span>\n                mp[<\/span>e]<\/span>=<\/span>++<\/span>cnt;<\/span>\n            }<\/span>\n            w[<\/span>mp[<\/span>e]<\/span>]<\/span>.<\/span>push_back<\/span>(<\/span>{<\/span>a,<\/span>b,<\/span>c,<\/span>d}<\/span>)<\/span>;<\/span>\n        }<\/span>\n        q<\/span>(<\/span>1<\/span>,<\/span>100<\/span>,<\/span>100<\/span>,<\/span>100<\/span>,<\/span>100<\/span>)<\/span>;<\/span>\n        printf<\/span>(<\/span>\"%lldn\"<\/span>,<\/span>max1)<\/span>;<\/span>\n    }<\/span>\n}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-31","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/31","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=31"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/31\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=31"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=31"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=31"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}