UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211391#3806. 逃跑181126062312063ms4292kbC++111.9kb2024-08-11 10:00:022024-08-11 13:02:00

answer

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, k, a[11][200001], ans , b[200001];
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
bool vis[21];
void dfs(int x)
{
    if (x == n + 1)
    {
        int sum = 0, tot = 0, aa[11];
        memset(aa, 0, sizeof(aa));
        for (int i = 1; i <= n; i++)
        {
            if (vis[i])
            {
                tot++;
            }
        }
        if (tot != k)
        {
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            if (vis[i])
            {
                for (int j = 1; j <= m; j++)
                {
                    aa[j] += a[j][i];
                }
            }
        }
        for (int i = 1; i <= m; i++)
        {
            //cout << aa[i] << " ";
            sum += abs(aa[i]);
        }
        //cout << endl;
        ans = max(ans, sum);
        return;
    }
    vis[x] = 1;
    dfs(x + 1);
    vis[x] = 0;
    dfs(x + 1);
}
signed main()
{
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            a[j][i] = read();
        }
    }
    if(m==1)
    {
        int aa=0,bb=0;
        for (int i = 1; i <= n; i++)
        {
            b[i]=a[1][i];
        }
        sort(b+1,b+n+1);
        for (int i = 1; i <= k; i++)
        {
            aa+=abs(b[i]);
        }
        for(int i = n; i >= n - k; i--)
        {
            bb+=abs(b[i]);
        }
        printf("%lld",max(aa,bb));
    }
    else
    {
        dfs(1); 
        printf("%lld", ans);
    }
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 3ms
memory: 1184kb

input:

16 6 10
-8117570516 9044069943 -8048766531 -8085807376 9028744360 -2291836940
8616476021 250513762 9...

output:

231924481827

result:

ok "231924481827"

Test #2:

score: 10
Accepted
time: 8ms
memory: 1192kb

input:

18 8 15
-6677000484 -1719283852 4578001104 8068813014 -80018326 4784041624 -1445243501 5746477070
-4...

output:

266922244841

result:

ok "266922244841"

Test #3:

score: 0
Wrong Answer
time: 15ms
memory: 2732kb

input:

100000 1 30000
-8076175068
4904794051
9104341999
1200537137
7000920774
9670819374
-8604644357
-63778...

output:

210328163704200

result:

wrong answer 1st words differ - expected: '210324135222440', found: '210328163704200'

Test #4:

score: 0
Wrong Answer
time: 37ms
memory: 4292kb

input:

200000 1 150000
-2272499492
-8807500507
3725379627
7512017895
4166123214
1269935574
-8584261761
-751...

output:

625365836395687

result:

wrong answer 1st words differ - expected: '378098351320197', found: '625365836395687'

Test #5:

score: 0
Time Limit Exceeded

input:

100000 2 50000
5241196316 8333678776
-5242651186 5299526105
9464328294 -6643098907
-7209213944 -2118...

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

100000 3 77777
-6171366053 3327407178 6863027058
-2358761813 -865379553 7668502806
-1462046286 16445...

output:


result:


Test #7:

score: 0
Time Limit Exceeded

input:

100000 4 80000
1342329756 468586460 -1031261932 -4571220835
8804945368 3053813574 4285088604 5648487...

output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

100000 5 50000
2090638820 9317267787 6793358676 4188448984 -9559977197
7940656860 -2874312253 -64757...

output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

200000 7 150000
9971130068 -8676993799 6080041194 -2943164240 -8998382194 9328104368 -6115122293
-24...

output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

200000 8 190000
1307391941 4980087558 -8998121420 3485381411 -4347578759 3621016169 4723154919 80775...

output:


result: