Submission #929187

#	Time	Username	Problem	Language	Result	Execution time	Memory
929187		Stavab	Colouring a rectangle (eJOI19_colouring)	C++14	20 / 100	82 ms	14672 KiB

colouring

#include <iostream>

using namespace std;

#define INF 9999999999999999

int A[200005][2];
int B[200005][2];
long long prSum[200005][2];

int main()
{
    int N, M;
    scanf("%d %d", &N, &M);

    int input;
    for(int i = 0; i < 2; i++)
    {
        for(int j = 1; j <= N + M - 1; j++)
        {
            scanf("%d", &input);

            if(i == 0)
            {
                if(j % 2 == 1)
                    A[(j + 1) / 2][0] = input;
                else
                    A[j / 2][1] = input;
            }
            else
            {
                if(j % 2 == 1)
                    B[(j + 1) / 2][0] = input;
                else
                    B[j / 2][1] = input;
            }
        }
    }

    for(int i = 0; i < 2; i++)
        for(int j = 1; j <= N; j++)
            prSum[j][i] = prSum[j - 1][i] + B[j][i];


    long long answer = 0;

    if(N % 2 == 1)
    {
        long long tmpAnswer = INF;
        long long sum = 0;

        int size = (N + 1) / 2;
        for(int j = 0; j < size; j++)
        {
            tmpAnswer = min(tmpAnswer, sum + prSum[N - j][0] - prSum[j][0]);

            if(j == 0)
                sum += A[size][0];
            else
            {
                sum += A[size + j][0];
                sum += A[size - j][0];
            }
        }
        tmpAnswer = min(tmpAnswer, sum);
        answer += tmpAnswer;

        tmpAnswer = INF;
        sum = 0;
        size = (N - 1) / 2;
        for(int j = 0; j < size; j++)
        {
            tmpAnswer = min(tmpAnswer, sum + prSum[N - 1 - j][1] - prSum[j][1]);

            sum += A[size - j][1];
            sum += A[size + 1 + j][1];
        }
        tmpAnswer = min(tmpAnswer, sum);
        answer += tmpAnswer;
    }
    else
    {
        long long tmpAnswer = INF;
        long long sum = 0;

        int size = N / 2;
        for(int j = 0; j < size; j++)
        {
            tmpAnswer = min(tmpAnswer, sum + prSum[N - j][0] - prSum[j][0]);

            if(j == 0)
                sum += A[size][1];
            else
            {
                sum += A[size + j][1];
                sum += A[size - j][1];
            }
        }
        tmpAnswer = min(tmpAnswer, sum);
        answer += tmpAnswer;

        tmpAnswer = INF;
        sum = 0;
        size = N / 2;
        for(int j = 0; j < size; j++)
        {
            tmpAnswer = min(tmpAnswer, sum + prSum[N - 1 - j][1] - prSum[j][1]);

            sum += A[size - j][0];
            sum += A[size + 1 + j][0];
        }
        tmpAnswer = min(tmpAnswer, sum);
        answer += tmpAnswer;
    }

    printf("%lld\n", answer);

    return 0;
}

Compilation message (stderr)

colouring.cpp: In function 'int main()':
colouring.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
colouring.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |             scanf("%d", &input);
      |             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 10
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20