2019 牛客多校第六场

Garbage Classification

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

On the CVBB planet, garbage classification has been gradually executed to help save resources and protect the environment. Nowadays people have to be equipped with knowledge of distinguishing different types of garbage. Now, given the waste compositions of a discarded product, you are asked to determine which category it belongs to.
The waste compositions are represented as a string s consisting of only lowercase letters, where each letter represents a waste composition and has an equal proportion. Each waste composition in that product is in one of the three situations, dry, wet or harmful.
The product can be classified by the following rules:

  •  In case that at least 25% of its compositions is harmful, it is harmful garbage.
  •  In case that at most 10% of its compositions is harmful, it is recyclable garbage.
  •  In other cases, if the proportion of dry compositions in it is at least twice that of wet compositions, it is dry garbage, or otherwise, it is wet garbage.

输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤501 \leq T \leq 501≤T≤50), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains a non-empty string s (1≤∣s∣≤20001 \le |s| \le 20001≤∣s∣≤2000) consisting of only lowercase letters.

The second line contains a string t of length 26, consisting of only characters in {d,w,h}\lbrace d, w, h \rbrace{d,w,h}. The i-th character of t represents the situation of the waste composition denoted by the i-th lowercase letter, where 'd', 'w' and 'h' mean dry, wet or harmful respectively.

输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y (y∈{Harmful,Recyclable,Dry,Wet}y \in \lbrace \text{Harmful}, \text{Recyclable}, \text{Dry}, \text{Wet} \rbracey∈{Harmful,Recyclable,Dry,Wet}) denotes the garbage type of the product in this test case.

示例1

输入

4
dqxxjefgctjgdbqxphff
hddhddhhhdhdhwwddhhdwwdhhw
iqdvfzzdqsbdevzebego
wdhddwwhwhdhhhwwdwdhwdwhhd
erkjqzsmchcmbqeasadf
dwddddwdwdwhdwhhdhhwwhhwdh
mcxkwmxxlhbrymwawhio
ddhwhddhwwwdddwdwhwwwhdwdw

输出

Case #1: Harmful
Case #2: Recyclable
Case #3: Dry
Case #4: Wet

签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+10;
char s[2020],c[27];
int ca=0;
void solve(){
    scanf("%s",s+1);scanf("%s",c);
    int a[4]={0,},n=strlen(s+1);
    rep(i,1,n){
        if(c[s[i]-'a']=='d') a[1]++;
        else if(c[s[i]-'a']=='w') a[2]++;
        else if(c[s[i]-'a']=='h') a[3]++;
    }
    printf("Case #%d: ",++ca);
    if(a[3]*4>=n){puts("Harmful");return;}
    if(a[3]*10<=n){puts("Recyclable");return;}
    if(a[1]>=a[2]*2) puts("Dry");
    else puts("Wet");
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

 


Shorten IPv6 Address

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

You are given an IPv6 address which is a 128-bit binary string. Please determine its shortest representation according to the following rules:

  • Express the address in hexadecimal representation and use a colon ‘:’ to split every four hex digits. Every four digits are called a field. For example, ‘0000:0000:0123:4567:89ab:0000:0000:0000’.
  • Leading zeros in a field can be omitted. For example, the above IPv6 address can be shortened to ‘0:0:123:4567:89ab:0:0:0’.
  • Consecutive zero fields (with colons near them) consisting of at least two fields can be replaced by a double colon ‘::’. Besides, no more than one double colon can be used in an address. For example, the above IPv6 address can be shortened to ‘0:0:123:4567:89ab::’ or ‘::123:4567:89ab:0:0:0’, but not ‘::123:4567:89ab::’.
  • If there are multiple shortest forms of the same length, use the lexicographically (regard the shorten IPv6 address as string) smallest one.

If the above rules conflict with rules in the real world, please refer to the rules mentioned in this problem.

输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤10001 \leq T \leq 10001≤T≤1000), indicating the number of test cases. Test cases are given in the following.

Each test case consists of only one line, containing a 128-bit binary string.

输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

示例1

输入

3
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000010010001101000101011001111000100110101011000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000010010001100000000000000000000000000000000000000000000000001000101011001111000100110101011

输出

Case #1: ::
Case #2: 0:0:123:4567:89ab::
Case #3: 0:0:123::4567:89ab

签到题,注意删除中间的0和末尾的0对答案长度的影响不一样

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+10;
int ca=0;
char s[220];
void solve(){
    scanf("%s",s+1);
    printf("Case #%d: ",++ca);
    int a[10][5]={0,},pos=0,f[10]={0,};
    rep(i,1,8) rep(j,1,4) rep(k,1,4){
        a[i][j]+=(s[++pos]-'0')*(int)pow(2,4-k);
    }
    rep(i,1,8){
        int fl=1;
        rep(j,1,4){
            if(a[i][j]==0&&fl&&j<4) continue;
            else{
                if(a[i][j]==0&&fl&&j==4) f[i]=1;
                fl=0;
            }
        }
    }
    int num=0,p=1,tmp=0,ind=0;
    rep(i,1,8){
        if(f[i]){
            if(p==i-1) tmp++;
            else tmp=1;
            p=i;
            if(tmp>=num&&tmp>=2){
                num=tmp;
                if(ind==0) ind=i-num+1;
                else if(ind==1) ind=i-num+1;
                else if(i!=8) ind=i-num+1;
            }
        }
    }
    int flag=1;
    if(ind){
        if(ind==1) printf(":");
        rep(i,1,8){
            int fl=1;
            rep(j,1,4){
                if(a[i][j]==0&&fl&&j<4) continue;
                if(i>=ind&&i<=ind+num-1) continue;
                else{
                    fl=0;
                    if(a[i][j]<10) printf("%d",a[i][j]);
                    else printf("%c",'a'+a[i][j]-10);
                }
            }
            if(i>=ind&&i<=ind+num-1){
                if(flag) printf(":"),flag=0;
            }
            else if(i<8) printf(":");
        }

    }
    else{
        rep(i,1,8){
            int fl=1;
            rep(j,1,4){
                if(a[i][j]==0&&fl&&j<4) continue;
                else{
                    fl=0;
                    if(a[i][j]<10) printf("%d",a[i][j]);
                    else printf("%c",'a'+a[i][j]-10);
                }
            }
            if(i<8) printf(":");
        }
    }
    puts("");
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

 


Move

时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

After the struggle of graduating from college, TangTang is about to move from a student apartment to his new home.

TangTang has n items to move, the i-th of which is of volume viv_ivi​. He can pack all these items into at most K boxes of the same volume.

TangTang is so clever that he uses the following strategies for packing items:
– Each time, he would put items into a box by the next strategy, and then he would try to fill another box. – For each box, he would put an unpacked item of the largest suitable volume into the box repeatedly until there is no such item that can be fitted in the box.
Now, the question is what is the minimum volume of these boxes required to pack all items.

输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤201 \leq T \leq 201≤T≤20), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers n, K (1≤n,K≤10001 \leq n, K \leq 10001≤n,K≤1000), representing the number of items and the number of boxes respectively.

The second line contains n integers v1v_1v1​, v2v_2v2​, …\ldots…, vnv_nvn​ (1≤v1,v2,…,vn≤10001 \leq v_1, v_2, \ldots, v_n \leq 10001≤v1​,v2​,…,vn​≤1000), where the i-th integer viv_ivi​ represents the volume of the i-th item.

输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

示例1

输入

1
5 3
1 2 3 4 5

输出

Case #1: 5

暴力枚举答案判断,注意没有二分性
比如:
15
39 39 39 39 39 60 60 60 60 60 100 100 100 100 100
199 为一个合法的答案,但 200 不是,201 也不是。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define pii pair<int,int>
typedef long long ll;
int casd,l,r,mid,cas,z,x,n,m,w,h,a[1010],b[1010];
bool cmp(int yi,int er){
    return yi>er;
}
bool kk(int u){
    for (int i=1;i<=x;i++)
      b[i]=u;
    for (int i=1;i<=z;i++){
        n=0;
        for (int j=1;j<=x;j++)
          if (b[j]>=a[i]) {n=j;break;}
        if (!n) return 0;
        b[n]-=a[i];
    }
    return 1;
}
int main(){
    casd=0;
    scanf("%d",&cas);
    while (cas--){
        printf("Case #%d: ",++casd);
        scanf("%d%d",&z,&x);
        int sum=0;
        for (int i=1;i<=z;i++) scanf("%d",&a[i]),sum=max(sum,a[i]);
        int low=sum;
        sort(a+1,a+z+1,cmp);
        l=low;r=10000000;int ans=1;
        rep(i,1,log(z)){
            while (l<=r){
                mid=l+(r-l)/2;
                if (kk(mid)) ans=mid,r=mid-1; else l=mid+1;
            }
            l=low;r=ans;
        }
        printf("%d\n",ans);
    }
    return 0;
}

 


Androgynos

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H. The complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Give a positive integer n, check whether there exists a simple undirected graph G having n vertices, which is isomorphic to its complement graph H. If the graphs G and H exist, report them with any possible isomorphism.

输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤51 \leq T \leq 51≤T≤5), indicating the number of test cases. Test cases are given in the following.

Each test case consists of only one line, containing an integer n (1≤n≤20001 \leq n \leq 20001≤n≤2000).

输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y (y∈{Yes,No}y \in \lbrace \text{Yes}, \text{No} \rbracey∈{Yes,No}) denotes whether or not the graphs exist in this test case.

If the graphs exist, then output (n + 1) extra lines.

The first n lines represent the graph G, where each line contains a binary string of length n. In the i-th line, the j-th character Gi,jG_{i, j}Gi,j​ is '1' when the i-th vertex and the j-th one are adjacent, or otherwise, in case they are not adjacent, Gi,jG_{i, j}Gi,j​ is '0'. Note that Gi,iG_{i, i}Gi,i​ must be '0' and Gi,jG_{i, j}Gi,j​ must be the same as Gj,iG_{j, i}Gj,i​.

The last line contains n space-separated integers f1f_1f1​, f2f_2f2​, …\ldots…, fnf_nfn​, representing an isomorphism of graphs G and H in which the i-th vertex in the graph G is mapped to the fif_ifi​-th vertex in the complement graph H. Note that every two consecutive integers in one line should be separated by a single space, please do not add any tailing space in your output\text{please do not add any tailing space in your output}please do not add any tailing space in your output. 

示例1

输入

4
1
2
3
4

输出

Case #1: Yes
0
1
Case #2: No
Case #3: No
Case #4: Yes
0100
1010
0101
0010
2 4 1 3

首先两个图同构有个必要条件是边数要相同,也就是说n阶完全图的边数得是偶数

若 n = 4k:
先考虑一个更简单的情况,n=4,相信大家都会手构(如果你不会,还可以枚举映射关系跑个2sat);观察n=4的情况,容易发现,可以将顶点分为两组,使得i和fi都来自不同组;容易想到:原图中的团在补图中会变成独立集。

对于n=4k(>1)的情况,可以先把顶点分成4块,2块内部连成团,2块内部不连组成独立集,然后按n=4的情况连块之间的边即可

若n = 4k + 1:多出的一个点向所有团连边即可

若n = 4k + 2 或 4k + 3:无解

#include <bits/stdc++.h>
using namespace std;
int s[2050][2050];
int main(){
    int T;
    scanf("%d",&T);
    int ca=0;
    while(T--){
        ca++;
        int n;
        scanf("%d",&n);
        printf("Case #%d: ",ca);
        if(n==1){
            printf("Yes\n0\n1\n");
        }
        else if(n%4>1){
            printf("No\n");
        }
        else{
            int k=n/4;
            printf("Yes\n");
            memset(s,0,sizeof(s));
            for(int i=0;i<k;i++){
                for(int j=0;j<k;j++){
                    for(int l=0;l<=2;l++) s[i*4+l][j*4+l+1]=s[j*4+l+1][i*4+l]=1;
                    if(i==j) continue;
                    s[i*4][j*4]=s[i*4+3][j*4+3]=1;
                }
            }
            if(n%4==1){
                for(int i=0;i<k;i++) s[n-1][i*4]=s[n-1][i*4+3]=s[i*4+3][n-1]=s[i*4][n-1]=1;
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    printf("%d",s[i][j]);
                }
                printf("\n");
            }
            for(int i=0;i<k;i++){
                if(i!=0) printf(" ");
                printf("%d %d %d %d",i*4+2,i*4+4,i*4+1,i*4+3);
            }
            if(n%4==1) printf(" %d",n);
            printf("\n");
        }
    }
    return 0;
}

 


Is Today Friday?

时间限制:C/C++ 5秒,其他语言10秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

No, it’s not Friday 🙁

TangTang loves Friday and he has made up a list of n days which are all Friday! Each date in this list is formed as “yyyy/mm/dd”, where “yyyy” is a four-digit number representing the year, “mm” is a two-digit number representing the month and “dd” is a two-digit number representing the day. TangTang only considers years between 1600 and 9999 (inclusive), so each year in the list always has four digits, but the months and the days may have leading zeros when it’s necessary. For example, “August 3rd, 2019” should be formed as “2019/08/03”.

To store safely, TangTang ciphered the list using a simple substitution cipher. He substituted each digit by a letter between ‘A’ and ‘J’ such that the same digits correspond to the same letter and different digits to different letters.

Unfortunately, TangTang forgot which letter corresponds to which digit. Please help him restore the original list.

输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤101 \leq T \leq 101≤T≤10), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains an integer n (1≤n≤1000001 \leq n \leq 1000001≤n≤100000), indicating the number of dates.

Each of the next n lines contains a string in the form of "yyyy/mm/dd", representing a ciphered date, where each digit is substituted by an uppercase letter between 'A' and 'J'.

输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

If there is no way to restore the list, then y is "Impossible".

Otherwise, y is a string consisting of ten distinct digits, representing the key to decipher the list. More specifically, the i-th digit in y corresponds to the i-th uppercase letter.

If there are at least two ways, then y is the smallest possible string in the lexicographical order.

示例1

输入

2
1
CABJ/AI/AC
5
CABJ/AI/AC
CABJ/AI/AD
CABJ/AI/AE
CABJ/AI/AF
CABJ/AI/AG

输出

Case #1: 0123456789
Case #2: Impossible

蔡勒公式
对于任何一个加密后的日期,只有几万个排列能将其映射到合法日期。
只对前若干个日期求出所有合法的排列后,再依次检查是否对所有日期合法。
坑点:有重复的日期,需要去重。

#include <bits/stdc++.h>
using namespace std;
char s[3630000][11],tmp[11];
int cnt=1,mk[10];
int lim[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
void init(int pos){
    if(pos==10){
        for(int i=0;i<pos;i++) s[cnt][i]=tmp[i];
        cnt++;
        return;
    }
    for(int i=0;i<10;i++){
        if(!mk[i]){
            mk[i]=1;
            tmp[pos]='0'+i;
            init(pos+1);
            mk[i]=0;
        }
    }
    return;
}
int judge(int pt,string& ss){
    int y=0;
    for(int i=0;i<=3;i++){
        y*=10;
        y+=s[pt][ss[i]-'A']-'0';   
    }
    int mo=0;
    for(int i=5;i<=6;i++){
        mo*=10;
        mo+=s[pt][ss[i]-'A']-'0';
    }
    int d=0;
    for(int i=8;i<=9;i++){
        d*=10;
        d+=s[pt][ss[i]-'A']-'0';
    }
    if((y%4==0 && y%100!=0)|| y%400==0) lim[2]=29;
    else lim[2]=28;
    if(y<1600 || mo<=0 || mo>12 || d<=0 || d>lim[mo]) return 0;
    if(mo<=2){
        mo+=12;
        y--;
    }
    int w=(d+2*mo+3*(mo+1)/5+y+y/4-y/100+y/400+1)%7;
    return w==5;
}
int ju[3630000];
string q[100100];
int main(){
    init(0);
    int T;
    int ca=0;
    scanf("%d",&T);
    while(T--){
        ca++;
        int n;
        scanf("%d",&n);
        memset(ju,0,sizeof(ju));int num=cnt;
        for(int i=1;i<=n;i++) cin>>q[i];
        sort(q+1,q+1+n);
        n=unique(q+1,q+1+n)-q-1;
        for(int i=1;i<=min(n,10);i++){
            for(int j=1;j<cnt;j++){
                if(ju[j]==1) continue;
                if(judge(j,q[i])==0){
                    ju[j]=1;
                    num--;
                }
            }
        }
        vector<int> v,vv;
        for(int i=1;i<cnt;i++){
            if(ju[i]==0){
                v.push_back(i);
                vv.push_back(1);
            }
        }
        int ccnt=(int)v.size();
        for(int i=11;i<=n;i++){
            for(int j=0;j<(int)v.size();j++){
                if(vv[j]){
                    int fg = judge(v[j],q[i]);
                    if(!fg) vv[j]=0,ccnt--;
                }
            }
        }
        printf("Case #%d: ",ca);
        if(ccnt==0){
            printf("Impossible\n");
        }
        else{
            for(int i=0;i<(int)v.size();i++){
                if(vv[i]){
                    for(int j=0;j<10;j++){
                        printf("%c",s[v[i]][j]);
                    }
                    printf("\n");
                    break;
                }
            }
        }
    }
    return 0;
}

 


Upgrading Technology

时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

Rowlet is playing a very popular game in the pokemon world. Recently, he has encountered a problem and wants to ask for your help.

In this game, there is a technology tree system. There are n kinds of technology in this game, each of them has m levels numbered from 1 to m. In the beginning, all technologies have no level (regard as level 0). When the i-th technology is at the (j – 1)-th level, the player can pay cijc_{i j}cij​ pokedollars (currency used in this game) to upgrade this technology into the j-th level. However, sometimes upgrading is so easy that the cost might be negative, which implies the player may gain profit from upgrading technologies.

Moreover, if all technologies have been upgraded to level j, the player will gain an additional profit of djd_{j}dj​ pokedollars. However, sometimes too many technologies of the same level might be confusing, hence the profit can be negative as well.

Rowlet wants to determine the optimal strategy that can bring him the most pokedollars. Help him to find the maximum gain. Note that Rowlet may upgrade nothing, and in that case, the profit is zero.

输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤101 \leq T \leq 101≤T≤10), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers n, m (1≤n,m≤10001 \leq n, m \leq 10001≤n,m≤1000), representing the number of technologies and the number of levels respectively.

The i-th of the next n lines contains m integers, where the j-th number is cijc_{i j}cij​ (−109≤cij≤109-10^{9} \leq c_{i j} \leq 10^{9}−109≤cij​≤109).

The last line contains m integers, where the j-th number is djd_{j}dj​ (−109≤dj≤109-10^{9} \leq d_{j} \leq 10^{9}−109≤dj​≤109).

We ensure that the sum of n⋅mn \cdot mn⋅m in all test cases is at most 2×1062 \times 10^{6}2×106.

输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer(in pokedollars) to this test case.

示例1

输入

2
2 2
1 2
2 -1
4 1
3 3
1 2 3
1 2 3
1 2 3
6 7 8

输出

Case #1: 2
Case #2: 4

说明

In the first example, Rowlet can upgrade the first technology to level 1 and the second technology to level 2, which costs 1 + 2 - 1 = 2 pokedollars, but Rowlet can get 4 pokedollars as the bonus of upgrading all technologies to level 1, so the answer is 4 - 2 = 2 pokedollars. 
In the second example, Rowlet can upgrade all technologies to level 2, which costs 1×3+2×3=91\times3 + 2\times3=91×3+2×3=9 pokedollars, but Rowlet can get 6 pokedollars as the bonus of upgrading all technologies to level 1 and 7 pokedollars as the bonus of upgrading all technologies to level 2, so the answer is 6 + 7 - 9 = 4 pokedollars.

一种错误的想法是枚举有 j 个 levl 升满,然后对第 i 种科技从 pre[i]j 到 pre[i]m] 中选择最小的那个作为第 i 种科技的最终 levl(这里 pre[i]j 表示第 i 种科技升前 j 个 levl 的代价和)

这种做法的问题在于 dj 可能是负的,贪心选取最小的 pre 可能导致 j+1 之后某些负的 levl使答案变差

但是稍微改一下就对了
枚举一种科技 i 作为 levl 最小的科技,并枚举它的 levl j,那么其它科技的 levl 就可以在j 到 m 之间任取了

当然你也可以dp
设 dp[i][j]表示前 i 种科技最小 levl 为 j 时,最小的 cost
转移方程为 dp[i+1][j=min(dp[i]k+pre[i+1][u),其中 k≥j,u≥j,且它们中至少有一个为j

#include <bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;
ll pre[1050][1050],a[1050][1050];
ll d[1050],pd[1050];
ll ppt[1050][1050];
void init(){
    for(int i=1;i<=n;i++){
        ppt[i][m]=m;
        for(int j=m-1;j>=0;j--){
            if(pre[i][j]<pre[i][ppt[i][j+1]]){
                ppt[i][j]=j;
            }
            else{
                ppt[i][j]=ppt[i][j+1];
            }
        }
    }
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    int ca=0;
    while(T--){
        ca++;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            pre[i][0]=0;
            for(int j=1;j<=m;j++){
                scanf("%lld",&a[i][j]);
                pre[i][j]=pre[i][j-1]+a[i][j];
            }
        }
        for(int i=1;i<=m;i++){
            scanf("%lld",&d[i]);
            pd[i]=pd[i-1]+d[i];
        }
        ll ans=0;
        init();
        for(int i=0;i<=m;i++){
            ll cnt=-pd[i];
            int fg=0;
            ll ma=-10000000000000000;
            for(int j=1;j<=n;j++){
                int pt=ppt[j][i];
                if(pt==i) fg=1;
                cnt+=pre[j][pt];
                ma=max(ma,pre[j][pt]-pre[j][i]);
            }
            if(!fg) cnt-=ma;
            ans=min(ans,cnt);
        }
        printf("Case #%d: %lld\n",ca,-ans);
    }
    return 0;
}

 

发表评论,支持MarkDown语法