{"id":10,"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-10-07-%e5%b9%b6%e6%9f%a5%e9%9b%86%e5%90%af%e5%8f%91%e5%bc%8f%e5%90%88%e5%b9%b6\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-10-07-%e5%b9%b6%e6%9f%a5%e9%9b%86%e5%90%af%e5%8f%91%e5%bc%8f%e5%90%88%e5%b9%b6","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-10-07-%e5%b9%b6%e6%9f%a5%e9%9b%86%e5%90%af%e5%8f%91%e5%bc%8f%e5%90%88%e5%b9%b6\/","title":{"rendered":"2020-10-07 \u5e76\u67e5\u96c6+\u542f\u53d1\u5f0f\u5408\u5e76"},"content":{"rendered":"

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

http:\/\/icpc.upc.edu.cn\/problem.php?cid=2592&pid=5<\/a><\/p>\n

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

DIDIDI and WNJXYK are good friends. One day, they go to the zoo. The monkeys are playing happily. There are n monkeys named 1-n. At first, the first one hangs its tail on the tree. The other n-1 monkeys, either are caught by other monkeys, or catch other monkeys, or both. In the next m seconds, every second, there will be a monkey releasing its left hand or right hand. And then some monkeys will drop on the floor. Given the relationship between monkeys, calculate the landing time of every monkey.<\/p>\n

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

The first line of input contains a positive integer T, telling you there are T test cases followed.
Each test case, first line includes two integers n, m. n means number of monkeys, and m as mentioned in the description.
Then following n lines, the k-th line has two integers, describe the k-th monkey\u2019s information. The first integer is the index of monkey in its left hand, the second integer is the index of monkey in its right hand. -1 indicates there is nothing in its hand.
Then following m lines, the i-th line gives the information at time i-1, every line has two numbers, the first is the index of the monkey, the second is the hand that it releases, 1 is left hand, 2 is right hand.
It\u2019s guaranteed that all the monkeys aren\u2019t on the floor at the beginning.<\/p>\n

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

For each test case, print a line \u201cCase #x: \u201d, where x is the case number (starting from 1) and print n integers. The i-th integer is the time monkey i drop in the floor. If monkey i don\u2019t land on the floor, print -1;<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
1\n3 2\n-1 3\n3 -1\n1 2\n1 2\n3 1\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
Case #1: -1 1 1\n<\/code><\/pre>\n
<\/a>\u63d0\u793a<\/h5>\n
Tips:1\u2264T\u226410,1\u2264n\u2264200,000,0\u2264m\u2264400,000
 Initially, the first monkey\u2019s tail hangs on the tree. The first monkey\u2019s right hand catches the third monkey, the second monkey\u2019s left hand catches the third monkey, and the third\u2019s left hand catches the first monkey while the right hand catches the second. On time 0, the first monkey releases its right hand, no monkey lands on the floor. On time 1, the third monkey releases its left hand, then the second monkey and the third land on the floor.<\/p>\n
<\/a>\u53c2\u8003\u535a\u5ba2<\/h5>\n
https:\/\/blog.csdn.net\/Cosmic_Tree\/article\/details\/108921892<\/a><\/p>\n
#pragma<\/span> GCC optimize(3)<\/span>\n#pragma<\/span> GCC optimize(\"Ofast\",\"unroll-loops\",\"omit-frame-pointer\",\"inline\")<\/span>\n#include<\/span> <\/span><\/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> x,<\/span>y;<\/span>\n}<\/span>;<\/span>\nint<\/span> ans[<\/span>200500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nnode a[<\/span>400500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> vis[<\/span>200500<\/span>]<\/span>[<\/span>3<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> g[<\/span>200500<\/span>]<\/span>[<\/span>2<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> father[<\/span>200500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nvector<<\/span>int<\/span>><\/span>deep[<\/span>200500<\/span>]<\/span>;<\/span>\nint<\/span> findfa<\/span>(<\/span>int<\/span> n)<\/span>\n{<\/span>\n    if<\/span>(<\/span>n==<\/span>father[<\/span>n]<\/span>)<\/span>\n        return<\/span> n;<\/span>\n    else<\/span>\n        return<\/span> father[<\/span>n]<\/span>=<\/span>findfa<\/span>(<\/span>father[<\/span>n]<\/span>)<\/span>;<\/span>\n}<\/span>\nint<\/span> union1<\/span>(<\/span>int<\/span> a,<\/span>int<\/span> b)<\/span>\n{<\/span>\n    int<\/span> fa=<\/span>findfa<\/span>(<\/span>a)<\/span>;<\/span>\n    int<\/span> fb=<\/span>findfa<\/span>(<\/span>b)<\/span>;<\/span>\n    if<\/span>(<\/span>fa==<\/span>fb)<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    if<\/span>(<\/span>deep[<\/span>fa]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>><\/span>deep[<\/span>fb]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>\n        swap<\/span>(<\/span>fa,<\/span>fb)<\/span>;<\/span>\n    father[<\/span>fa]<\/span>=<\/span>fb;<\/span>\n    deep[<\/span>fb]<\/span>.<\/span>insert<\/span>(<\/span>deep[<\/span>fb]<\/span>.<\/span>end<\/span>(<\/span>)<\/span>,<\/span>deep[<\/span>fa]<\/span>.<\/span>begin<\/span>(<\/span>)<\/span>,<\/span>deep[<\/span>fa]<\/span>.<\/span>end<\/span>(<\/span>)<\/span>)<\/span>;<\/span>\n}<\/span>\nint<\/span> union2<\/span>(<\/span>int<\/span> a,<\/span>int<\/span> b,<\/span>int<\/span> ans1)<\/span>\n{<\/span>\n    if<\/span>(<\/span>b==<\/span>-<\/span>1<\/span>)<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    int<\/span> fa=<\/span>findfa<\/span>(<\/span>a)<\/span>;<\/span>\n    int<\/span> fb=<\/span>findfa<\/span>(<\/span>b)<\/span>;<\/span>\n    if<\/span>(<\/span>fa==<\/span>fb)<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    int<\/span> f1=<\/span>findfa<\/span>(<\/span>1<\/span>)<\/span>;<\/span>\n    if<\/span>(<\/span>fa==<\/span>f1)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<<\/span>deep[<\/span>fb]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            ans[<\/span>deep[<\/span>fb]<\/span>[<\/span>i]<\/span>]<\/span>=<\/span>ans1;<\/span>\n        }<\/span>\n    }<\/span>\n    if<\/span>(<\/span>fb==<\/span>f1)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<<\/span>deep[<\/span>fa]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            ans[<\/span>deep[<\/span>fa]<\/span>[<\/span>i]<\/span>]<\/span>=<\/span>ans1;<\/span>\n        }<\/span>\n    }<\/span>\n    if<\/span>(<\/span>deep[<\/span>fa]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>><\/span>deep[<\/span>fb]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>\n        swap<\/span>(<\/span>fa,<\/span>fb)<\/span>;<\/span>\n    father[<\/span>fa]<\/span>=<\/span>fb;<\/span>\n    deep[<\/span>fb]<\/span>.<\/span>insert<\/span>(<\/span>deep[<\/span>fb]<\/span>.<\/span>end<\/span>(<\/span>)<\/span>,<\/span>deep[<\/span>fa]<\/span>.<\/span>begin<\/span>(<\/span>)<\/span>,<\/span>deep[<\/span>fa]<\/span>.<\/span>end<\/span>(<\/span>)<\/span>)<\/span>;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> t;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>t)<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> t1=<\/span>1<\/span>;<\/span>t1<=<\/span>t;<\/span>t1++<\/span>)<\/span>\n    {<\/span>\n        int<\/span> n,<\/span>m;<\/span>\n        scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m)<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            father[<\/span>i]<\/span>=<\/span>i;<\/span>\n            deep[<\/span>i]<\/span>.<\/span>clear<\/span>(<\/span>)<\/span>;<\/span>\n            deep[<\/span>i]<\/span>.<\/span>push_back<\/span>(<\/span>i)<\/span>;<\/span>\n            vis[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>=<\/span>vis[<\/span>i]<\/span>[<\/span>2<\/span>]<\/span>=<\/span>0<\/span>;<\/span>\n            ans[<\/span>i]<\/span>=<\/span>-<\/span>1<\/span>;<\/span>\n        }<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>g[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>,<\/span>&<\/span>g[<\/span>i]<\/span>[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>\n        }<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>m;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>a[<\/span>i]<\/span>.<\/span>x,<\/span>&<\/span>a[<\/span>i]<\/span>.<\/span>y)<\/span>;<\/span>\n            vis[<\/span>a[<\/span>i]<\/span>.<\/span>x]<\/span>[<\/span>a[<\/span>i]<\/span>.<\/span>y]<\/span>=<\/span>1<\/span>;<\/span>\n        }<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            if<\/span>(<\/span>vis[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>==<\/span>0<\/span>&&<\/span>g[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>!=<\/span>-<\/span>1<\/span>)<\/span>\n            {<\/span>\n                union1<\/span>(<\/span>i,<\/span>g[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>)<\/span>;<\/span>\n            }<\/span>\n            if<\/span>(<\/span>vis[<\/span>i]<\/span>[<\/span>2<\/span>]<\/span>==<\/span>0<\/span>&&<\/span>g[<\/span>i]<\/span>[<\/span>2<\/span>]<\/span>!=<\/span>-<\/span>1<\/span>)<\/span>\n            {<\/span>\n                union1<\/span>(<\/span>i,<\/span>g[<\/span>i]<\/span>[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>m;<\/span>i>=<\/span>1<\/span>;<\/span>i--<\/span>)<\/span>\n        {<\/span>\n            union2<\/span>(<\/span>a[<\/span>i]<\/span>.<\/span>x,<\/span>g[<\/span>a[<\/span>i]<\/span>.<\/span>x]<\/span>[<\/span>a[<\/span>i]<\/span>.<\/span>y]<\/span>,<\/span>i-<\/span>1<\/span>)<\/span>;<\/span>\n        }<\/span>\n        printf<\/span>(<\/span>\"Case #%d: \"<\/span>,<\/span>t1)<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            printf<\/span>(<\/span>\"%d \"<\/span>,<\/span>ans[<\/span>i]<\/span>)<\/span>;<\/span>\n        }<\/span>\n        printf<\/span>(<\/span>\"n\"<\/span>)<\/span>;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n
WNJXYK and DIDIDI are friends. They are thinking about getting strong all the time.
 They are playing a very hard online game and they can\u2019t defeat any monster in this game now. If they can\u2019t defeat monsters, they will not get EXP and will not get strong forever. They finally found that the only way for them to get strong is to upgrade their equipment with their limited coins. Each equipment can be upgrade many times with paying some money. And of course, they will get power from each upgrade.
 They have N equipment in total and each equipment can be upgrade for Ki times. At first, equipment are all in Level 0. If you upgrade the ith equipment from Level j-1 to Level j, you will pay Cij coins and get Wij power. They have M coins in total and they want to know the most power they can get with these coins.<\/p>\n
<\/a>\u8f93\u5165<\/h5>\n
The first line of input contains a positive integer T telling you there are T test cases followed.
 In each Test Case, there is two positive integers N,M in the first line indicates that there are N equipment and M coins.
 The following N Lines, there is a positive integer Ki at first indicates that the ith equipment can be upgrade Ki times. And there are 2Ki positive integers followed Wij,Cij.<\/p>\n
<\/a>\u8f93\u51fa<\/h5>\n
You need to output one line for each Test Case. \u201cCase #X: Y\u201d means the max power they can get in Xth Test Case is Y.<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
1
 3 5
 1 1 1
 2 1 1 5 4
 1 5 3<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
Case #1: 7<\/p>\n
<\/a>\u63d0\u793a<\/h5>\n
Tips:1\u2264T\u226410,1\u2264N\u226420,0\u2264M\u22641e9,0\u2264Ki\u22644,1\u2264Cij,Wij\u22641e9
 In this Sample, they can upgrade their equipment like this and this is the only for them to get 7 power with 5 coins.
 \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n
<\/a>\u89e3\u6790<\/h5>\n
\u53cc\u5411DFS+\u4e8c\u5206\u4f18\u5316<\/p>\n
#pragma<\/span> GCC optimize(3)<\/span>\n#pragma<\/span> GCC optimize(\"Ofast\",\"unroll-loops\",\"omit-frame-pointer\",\"inline\")<\/span>\n#include<\/span> <\/span><\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nconst<\/span> ll INF=<\/span> 1e18<\/span>;<\/span>\nstruct<\/span> node\n{<\/span>\n    ll x,<\/span>y;<\/span>\n}<\/span>;<\/span>\nll sum1[<\/span>100<\/span>]<\/span>[<\/span>100<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nll p1[<\/span>100<\/span>]<\/span>[<\/span>100<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nll n,<\/span>m;<\/span>\nnode ans[<\/span>5005000<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nll max1=<\/span>-<\/span>INF;<\/span>\nll cnt=<\/span>0<\/span>;<\/span>\nll size1[<\/span>100<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nbool<\/span> cmp<\/span>(<\/span>node a,<\/span>node b)<\/span>\n{<\/span>\n    return<\/span> a.<\/span>y<<\/span>b.<\/span>y;<\/span>\n}<\/span>\nll dfs1<\/span>(<\/span>ll k,<\/span>ll e,<\/span>ll sum,<\/span>ll p)<\/span>\n{<\/span>\n    if<\/span>(<\/span>k><\/span>e)<\/span>\n    {<\/span>\n        ans[<\/span>++<\/span>cnt]<\/span>=<\/span>node{<\/span>sum,<\/span>p}<\/span>;<\/span>\n        max1=<\/span>max<\/span>(<\/span>max1,<\/span>sum)<\/span>;<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    }<\/span>\n    for<\/span>(<\/span>ll i=<\/span>0<\/span>;<\/span> i<=<\/span>size1[<\/span>k]<\/span>;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>p+<\/span>p1[<\/span>k]<\/span>[<\/span>i]<\/span>><\/span>m)<\/span>\n            continue<\/span>;<\/span>\n        dfs1<\/span>(<\/span>k+<\/span>1<\/span>,<\/span>e,<\/span>sum+<\/span>sum1[<\/span>k]<\/span>[<\/span>i]<\/span>,<\/span>p+<\/span>p1[<\/span>k]<\/span>[<\/span>i]<\/span>)<\/span>;<\/span>\n    }<\/span>\n    dfs1<\/span>(<\/span>k+<\/span>1<\/span>,<\/span>e,<\/span>sum,<\/span>p)<\/span>;<\/span>\n}<\/span>\nll find1<\/span>(<\/span>ll num)<\/span>\n{<\/span>\n    ll l=<\/span>1<\/span>,<\/span>r=<\/span>cnt+<\/span>1<\/span>;<\/span>\n    while<\/span>(<\/span>l<<\/span>r)<\/span>\n    {<\/span>\n        ll mid=<\/span>(<\/span>l+<\/span>r)<\/span>\/<\/span>2<\/span>;<\/span>\n        if<\/span>(<\/span>ans[<\/span>mid]<\/span>.<\/span>y<<\/span>num)<\/span>\n            l=<\/span>mid+<\/span>1<\/span>;<\/span>\n        else<\/span> if<\/span>(<\/span>ans[<\/span>mid]<\/span>.<\/span>y><\/span>num)<\/span>\n            r=<\/span>mid;<\/span>\n        else<\/span> if<\/span>(<\/span>ans[<\/span>mid]<\/span>.<\/span>y==<\/span>num)<\/span>\n            l=<\/span>mid+<\/span>1<\/span>;<\/span>\n    }<\/span>\n    if<\/span>(<\/span>ans[<\/span>l-<\/span>1<\/span>]<\/span>.<\/span>y<=<\/span>num)<\/span>\n        return<\/span> l-<\/span>1<\/span>;<\/span>\n    else<\/span>\n        return<\/span> -<\/span>1<\/span>;<\/span>\n}<\/span>\nll dfs2<\/span>(<\/span>ll k,<\/span>ll e,<\/span>ll sum,<\/span>ll p)<\/span>\n{<\/span>\n    if<\/span>(<\/span>k><\/span>e)<\/span>\n    {<\/span>\n        ll pos=<\/span>find1<\/span>(<\/span>m-<\/span>p)<\/span>;<\/span>\n        if<\/span>(<\/span>~<\/span>pos)<\/span>\n            max1=<\/span>max<\/span>(<\/span>max1,<\/span>sum+<\/span>ans[<\/span>pos]<\/span>.<\/span>x)<\/span>;<\/span>\n        max1=<\/span>max<\/span>(<\/span>max1,<\/span>sum)<\/span>;<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    }<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span> i<=<\/span>size1[<\/span>k]<\/span>;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>p+<\/span>p1[<\/span>k]<\/span>[<\/span>i]<\/span>><\/span>m)<\/span>\n            continue<\/span>;<\/span>\n        dfs2<\/span>(<\/span>k+<\/span>1<\/span>,<\/span>e,<\/span>sum+<\/span>sum1[<\/span>k]<\/span>[<\/span>i]<\/span>,<\/span>p+<\/span>p1[<\/span>k]<\/span>[<\/span>i]<\/span>)<\/span>;<\/span>\n    }<\/span>\n    dfs2<\/span>(<\/span>k+<\/span>1<\/span>,<\/span>e,<\/span>sum,<\/span>p)<\/span>;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> t;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>t)<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> t1=<\/span>1<\/span>;<\/span> t1<=<\/span>t;<\/span> t1++<\/span>)<\/span>\n    {<\/span>\n        scanf<\/span>(<\/span>\"%lld%lld\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m)<\/span>;<\/span>\n        cnt=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            scanf<\/span>(<\/span>\"%lld\"<\/span>,<\/span>&<\/span>size1[<\/span>i]<\/span>)<\/span>;<\/span>\n            for<\/span>(<\/span>ll j=<\/span>1<\/span>;<\/span> j<=<\/span>size1[<\/span>i]<\/span>;<\/span> j++<\/span>)<\/span>\n            {<\/span>\n                ll x,<\/span>y;<\/span>\n                scanf<\/span>(<\/span>\"%lld%lld\"<\/span>,<\/span>&<\/span>sum1[<\/span>i]<\/span>[<\/span>j]<\/span>,<\/span>&<\/span>p1[<\/span>i]<\/span>[<\/span>j]<\/span>)<\/span>;<\/span>\n                sum1[<\/span>i]<\/span>[<\/span>j]<\/span>+<\/span>=<\/span>sum1[<\/span>i]<\/span>[<\/span>j-<\/span>1<\/span>]<\/span>;<\/span>\n                p1[<\/span>i]<\/span>[<\/span>j]<\/span>+<\/span>=<\/span>p1[<\/span>i]<\/span>[<\/span>j-<\/span>1<\/span>]<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        max1=<\/span>-<\/span>INF;<\/span>\n        dfs1<\/span>(<\/span>1<\/span>,<\/span>n\/<\/span>2<\/span>,<\/span>0<\/span>,<\/span>0<\/span>)<\/span>;<\/span>\n        sort<\/span>(<\/span>ans+<\/span>1<\/span>,<\/span>ans+<\/span>1<\/span>+<\/span>cnt,<\/span>cmp)<\/span>;<\/span>\n        ans[<\/span>0<\/span>]<\/span>.<\/span>x=<\/span>-<\/span>INF;<\/span>\n        for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span> i<=<\/span>cnt;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            ans[<\/span>i]<\/span>.<\/span>x=<\/span>max<\/span>(<\/span>ans[<\/span>i-<\/span>1<\/span>]<\/span>.<\/span>x,<\/span>ans[<\/span>i]<\/span>.<\/span>x)<\/span>;<\/span>\n        }<\/span>\n        dfs2<\/span>(<\/span>n\/<\/span>2<\/span>+<\/span>1<\/span>,<\/span>n,<\/span>0<\/span>,<\/span>0<\/span>)<\/span>;<\/span>\n        printf<\/span>(<\/span>\"Case #%d: %lldn\"<\/span>,<\/span>t1,<\/span>max1)<\/span>;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/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-10","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\/10","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=10"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/10\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=10"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=10"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=10"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
http:\/\/icpc.upc.edu.cn\/problem.php?cid=2592&pid=7<\/a><\/p>\n