Submission #919453

#	Time	Username	Problem	Language	Result	Execution time	Memory
919453		raphaelp	Colouring a rectangle (eJOI19_colouring)	C++14	30 / 100	248 ms	17772 KiB

colouring

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long M, N;
    cin >> M >> N;
    vector<long long> GD(N + M - 1), DG(N + M - 1);
    for (long long i = 0; i < N + M - 1; i++)
    {
        cin >> GD[i];
    }
    for (long long i = 0; i < N + M - 1; i++)
    {
        cin >> DG[i];
    }
    if (M == 1)
    {
        long long tot = 0;
        for (long long i = 0; i < N; i++)
        {
            tot += min(DG[i], GD[N - i - 1]);
        }
        cout << tot;
    }
    if (M == N)
    {
        vector<long long> mainDG(N + 1), mainGD(N + 1);
        for (long long i = 0; i < N + M - 1; i++)
        {
            if (i < N)
                mainDG[N - i] += DG[i];
            else
                mainDG[i - N + 2] += DG[i];
            if (i < N)
                mainGD[N - i] += GD[i];
            else
                mainGD[i - N + 2] += GD[i];
        }
        for (long long i = 2; i <= N; i++)
        {
            mainDG[i] += mainDG[i - 2];
            mainGD[i] += mainGD[i - 2];
        }
        long long best = 123456789000000000;
        long long buff = N;
        for (long long i = 0; i <= N; i += 2)
        {
            buff = max(buff, (long long)0);
            best = min(best, mainGD[i] + mainDG[buff]);
            buff -= 2;
            if (i == 0)
                i--;
        }
        long long best2 = 123456789000000000;
        buff = N - 1;
        for (long long i = 0; i <= N; i += 2)
        {
            buff = max(buff, (long long)0);
            best2 = min(best2, mainGD[i] + mainDG[buff]);
            buff -= 2;
        }
        cout << best + best2;
    }
}

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