oj.uz

Submission #929199

# Submission time Handle Problem Language Result Execution time Memory
929199 2024-02-17T22:40:45 Z Stavab Colouring a rectangle (eJOI19_colouring) C++14
20 / 100
 90 ms 6672 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 6592 KB Output is correct
2 Correct 67 ms 6588 KB Output is correct
3 Correct 90 ms 6480 KB Output is correct
4 Correct 69 ms 6592 KB Output is correct
5 Correct 69 ms 6508 KB Output is correct
6 Correct 62 ms 6672 KB Output is correct
7 Correct 68 ms 6592 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -