QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#42727	#4174. 学校食堂	MatrixCascade^#	100 ✓	90ms	71892kb	C++	1.7kb	2022-08-03 16:17:21	2022-08-03 16:17:24

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-08-03 16:17:24]
评测

测评结果：100
用时：90ms
内存：71892kb

查看

[2022-08-03 16:17:21]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int C;
int t[1031],b[1301];
int dp[1031][1<<9][33];
int n;
int main(){
    scanf("%d",&C);
    while(C--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%d%d",&t[i],&b[i]);
        }
        memset(dp,0x3f,sizeof(dp));
        dp[1][0][7]=0;
        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<(1<<8);++j)
            {
                for(int k=-8;k<=7;++k)
                {
                    if(dp[i][j][k+8]!=0x3f3f3f3f)
                    {
                        if(j&1)
                        {
                            dp[i+1][j>>1][k+7]=min(dp[i+1][j>>1][k+7],dp[i][j][k+8]);
                        }
                        else
                        {
                            int maxx=0x3f3f3f3f;
                            for(int r=0;r<=7;++r)
                            {
                                if(!((j>>r)&1))
                                {
                                    if(i+r>maxx)break;
                                    maxx=min(maxx,i+r+b[i+r]);
                                    //cout<<t[i+k]<<" "<<t[i+r]<<" "<<dp[i][j][k+8]<<" "<<dp[i][j|(i<<r)][r+8]<<i<<" "<<endl;
                                    dp[i][j|(1<<r)][r+8]=min(dp[i][j|(1<<r)][r+8],dp[i][j][k+8]+((i+k)?t[i+k]^t[i+r]:0));
                                }
                            }
                        }
                    }
                }
            }
        }
        int anss=0x3f3f3f3f;
        for(int i=0;i<=8;++i)
        {
            //cout<<dp[n][0][i]<<endl;
            anss=min(anss,dp[n+1][0][i]);
        }
        printf("%d\n",anss);
    }
    return 0;
}

源文件, 语言: C++

详细

Test #1:

score: 4

Accepted

time: 33ms

memory: 71736kb

input:

output:

result:

ok 4 lines

Test #2:

score: 4

Accepted

time: 32ms

memory: 71880kb

input:

output:

56
39
67

result:

ok 3 lines

Test #3:

score: 4

Accepted

time: 53ms

memory: 71736kb

input:

output:

result:

ok 5 lines

Test #4:

score: 4

Accepted

time: 33ms

memory: 71832kb

input:

output:

result:

ok 4 lines

Test #5:

score: 4

Accepted

time: 39ms

memory: 71816kb

input:

output:

result:

ok 5 lines

Test #6:

score: 4

Accepted

time: 23ms

memory: 71892kb

input:

output:

4325
3732
4403

result:

ok 3 lines

Test #7:

score: 4

Accepted

time: 40ms

memory: 71828kb

input:

output:

result:

ok 5 lines

Test #8:

score: 4

Accepted

time: 28ms

memory: 71752kb

input:

output:

992
1068
927

result:

ok 3 lines

Test #9:

score: 4

Accepted

time: 79ms

memory: 71828kb

input:

output:

result:

ok 5 lines

Test #10:

score: 4

Accepted

time: 70ms

memory: 71840kb

input:

output:

result:

ok 5 lines

Test #11:

score: 4

Accepted

time: 52ms

memory: 71840kb

input:

output:

result:

ok 4 lines

Test #12:

score: 4

Accepted

time: 54ms

memory: 71804kb

input:

output:

result:

ok 4 lines

Test #13:

score: 4

Accepted

time: 38ms

memory: 71876kb

input:

output:

50916
48160
48261

result:

ok 3 lines

Test #14:

score: 4

Accepted

time: 48ms

memory: 71812kb

input:

output:

result:

ok 4 lines

Test #15:

score: 4

Accepted

time: 54ms

memory: 71820kb

input:

output:

result:

ok 4 lines

Test #16:

score: 4

Accepted

time: 57ms

memory: 71828kb

input:

output:

result:

ok 4 lines

Test #17:

score: 4

Accepted

time: 78ms

memory: 71760kb

input:

output:

result:

ok 5 lines

Test #18:

score: 4

Accepted

time: 75ms

memory: 71820kb

input:

output:

result:

ok 5 lines

Test #19:

score: 4

Accepted

time: 56ms

memory: 71824kb

input:

output:

result:

ok 4 lines

Test #20:

score: 4

Accepted

time: 60ms

memory: 71732kb

input:

output:

result:

ok 4 lines

Test #21:

score: 4

Accepted

time: 43ms

memory: 71756kb

input:

output:

10772
10722
10383

result:

ok 3 lines

Test #22:

score: 4

Accepted

time: 43ms

memory: 71828kb

input:

output:

440367
428074
423337

result:

ok 3 lines

Test #23:

score: 4

Accepted

time: 46ms

memory: 71824kb

input:

output:

214852
215629
213471

result:

ok 3 lines

Test #24:

score: 4

Accepted

time: 90ms

memory: 71824kb

input:

output:

result:

ok 5 lines

Test #25:

score: 4

Accepted

time: 73ms

memory: 71832kb

input:

output:

result:

ok 4 lines