Submission #929199

#	Time	Username	Problem	Language	Result	Execution time	Memory
929199		Stavab	Colouring a rectangle (eJOI19_colouring)	C++14	20 / 100	90 ms	6672 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;

    if(N > M)
    {
        int K = N - M;

        for(int i = 0; i < 2; i++)
        {
            for(int j = 1; j <= 2*N - 1; j++)
            {
                if((i == 0 && j <= K) || (i == 1 && 2*N - 1 - j < K))
                    input = 0;
                else
                    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;
                }
            }
        }
    }
    else
    {
        int K = M - N;

        for(int i = 0; i < 2; i++)
        {
            for(int j = 1; j <= 2*M - 1; j++)
            {
                if((i == 1 && 2*N - 1 - j < K) || (i == 0 && 2*N - 1 - j < K))
                    input = 0;
                else
                    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:29:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |                     scanf("%d", &input);
      |                     ~~~~~^~~~~~~~~~~~~~
colouring.cpp:59:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |                     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