Submission #1075636

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1075636	2024-08-26T08:12:07 Z	Muhammad_Aneeq	Catfish Farm (IOI22_fish)	C++17	18 / 100	56 ms	10844 KB

fish

#include <vector>
using namespace std;
long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W)
{
    bool subt1=1,subt2=1,subt3=1,subt4=(N<=300);
    for (int i=0;i<M;i++)
    {
        if (X[i]%2)
            subt1=0;
        if (X[i]>1)
            subt2=0;
        if (Y[i]!=0)
            subt3=0;
        if (Y[i]>8)
            subt4=0;
    }
    if (subt1)
    {
        long long sm=0;
        for (int i=0;i<M;i++)
            sm+=W[i];
        return sm;
    }
    if (subt2)
    {
        long long sm[N]={};
        long long val[N][2]={};
        for (int i=0;i<M;i++)
            val[Y[i]][X[i]]=W[i];
        sm[0]=val[0][1];
        for (int i=1;i<N;i++)
            sm[i]=sm[i-1]+val[i][1];
        long long ans=sm[N-1];
        long long x=0;
        for (int i=0;i<N;i++)
        {
            x+=val[i][0];
            if (N>2)
                ans=max(ans,x+sm[N-1]-sm[i]);
        }
        ans=max(ans,x);
        return ans;
    }
    if (subt3)
    {
        long long dp[N][2]={};
        int val[N]={};
        for (int i=0;i<M;i++)
            val[X[i]]=W[i];
        dp[0][0]=0,dp[0][1]=val[0];
        long long ans=0;
        long long mx=0;
        for (int i=1;i<N;i++)
        {
            if (i>1)
                dp[i][0]=mx+val[i];
            if (i<N-1)
                dp[i][1]=max(dp[i][0],dp[i-1][0]+val[i]);
            mx=max(mx,max(dp[i-1][0],dp[i-1][1]));
            ans=max(ans,max(dp[i][0],dp[i][1]));
        }
        return ans;
    }
    if (subt4)
    {
        vector<vector<vector<long long>>>dp(2,vector<vector<long long>>(N,vector<long long>(9,0)));
        long long val[N][9]={};
        for (int i=0;i<M;i++)
            val[X[i]][Y[i]]=W[i];
        int pre[N][9]={};
        for (int i=0;i<N;i++)
        {
            pre[i][0]=val[i][0];
            for (int j=1;j<9;j++)
                pre[i][j]=pre[i][j-1]+val[i][j];
        }
        long long mx[N]={};
        long long ans=0;
        for (int i=0;i<9;i++)
            dp[1][0][i]=pre[0][i];
        for (int i=0;i<9;i++)
            dp[0][1][i]=pre[1][i];
        mx[0]=pre[0][8];
        for (int i=1;i<N;i++)
        {
            for (int j=0;j<9;j++)
            {
                if (i>1)
                    dp[0][i][j]=mx[i-2]+pre[i][j];
                if (i>2)
                    dp[0][i][j]=max(dp[0][i][j],mx[i-3]+pre[i][j]+pre[i-1][8]-pre[i-1][j]);
                if (i+1<N)
                {
                    dp[1][i][j]=max(dp[0][i][j],dp[0][i-1][8]+pre[i][j]);
                    if (j>0)
                        dp[1][i][j]=max(dp[1][i][j],dp[1][i-1][j-1]+val[i][j]);
                }
            }
            mx[i]=max(mx[i-1],max(dp[0][i][8],dp[1][i][8]));
        }
        for (int i=0;i<N;i++)
            for (int j=0;j<9;j++)
                ans=max(ans,max(dp[0][i][j],dp[1][i][j]));
        return ans;
    }
    return 0;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2136 KB	Output is correct
2	Correct	17 ms	2652 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	56 ms	7276 KB	Output is correct
6	Correct	55 ms	7256 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	33 ms	9152 KB	Output is correct
3	Correct	41 ms	10844 KB	Output is correct
4	Correct	15 ms	3532 KB	Output is correct
5	Correct	18 ms	4440 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	18 ms	5860 KB	Output is correct
13	Correct	19 ms	6744 KB	Output is correct
14	Correct	20 ms	5728 KB	Output is correct
15	Correct	19 ms	6236 KB	Output is correct
16	Correct	17 ms	5856 KB	Output is correct
17	Correct	19 ms	6204 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	2 ms	2140 KB	Output is correct
3	Correct	10 ms	3416 KB	Output is correct
4	Correct	8 ms	3676 KB	Output is correct
5	Correct	18 ms	6336 KB	Output is correct
6	Correct	18 ms	5464 KB	Output is correct
7	Correct	20 ms	6232 KB	Output is correct
8	Correct	19 ms	6196 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	344 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	420 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	424 KB	Output is correct
8	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '2', found: '1'
9	Halted	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	344 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	420 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	424 KB	Output is correct
8	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '2', found: '1'
9	Halted	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	344 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	420 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	424 KB	Output is correct
8	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '2', found: '1'
9	Halted	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	2 ms	2140 KB	Output is correct
3	Correct	10 ms	3416 KB	Output is correct
4	Correct	8 ms	3676 KB	Output is correct
5	Correct	18 ms	6336 KB	Output is correct
6	Correct	18 ms	5464 KB	Output is correct
7	Correct	20 ms	6232 KB	Output is correct
8	Correct	19 ms	6196 KB	Output is correct
9	Incorrect	17 ms	3932 KB	1st lines differ - on the 1st token, expected: '99999', found: '0'
10	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2136 KB	Output is correct
2	Correct	17 ms	2652 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	56 ms	7276 KB	Output is correct
6	Correct	55 ms	7256 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	33 ms	9152 KB	Output is correct
9	Correct	41 ms	10844 KB	Output is correct
10	Correct	15 ms	3532 KB	Output is correct
11	Correct	18 ms	4440 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	18 ms	5860 KB	Output is correct
19	Correct	19 ms	6744 KB	Output is correct
20	Correct	20 ms	5728 KB	Output is correct
21	Correct	19 ms	6236 KB	Output is correct
22	Correct	17 ms	5856 KB	Output is correct
23	Correct	19 ms	6204 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	2 ms	2140 KB	Output is correct
26	Correct	10 ms	3416 KB	Output is correct
27	Correct	8 ms	3676 KB	Output is correct
28	Correct	18 ms	6336 KB	Output is correct
29	Correct	18 ms	5464 KB	Output is correct
30	Correct	20 ms	6232 KB	Output is correct
31	Correct	19 ms	6196 KB	Output is correct
32	Correct	0 ms	344 KB	Output is correct
33	Correct	0 ms	344 KB	Output is correct
34	Correct	0 ms	344 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	420 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	0 ms	424 KB	Output is correct
39	Incorrect	0 ms	348 KB	1st lines differ - on the 1st token, expected: '2', found: '1'
40	Halted	0 ms	0 KB	-

Submission #1075636

Compilation message