CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:andreibe
Submission time:2023-10-30 23:38:35 +0200
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

input/code.cpp:77:1: error: '::main' must return 'int'
   77 | ll main()
      | ^~
input/code.cpp: In function 'int main()':
input/code.cpp:164:20: warning: unused variable 'oikeaArvo' [-Wunused-variable]
  164 |                 ll oikeaArvo;
      |                    ^~~~~~~~~

Code

#include <iostream>
#include <string>
#include <math.h>
#include <map>
#include <algorithm>
#include <vector>
#include <fstream>
#include <set>
#include <unordered_map>
#include <queue>
#include <chrono>
#include <climits>
#include <stack>
using namespace std;
using namespace std::chrono;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define S second
#define F first
// #define A 999999999999999999LL
#define M 1000000007
#define N 202020
#define REDIR                 \
    ifstream in("input.txt"); \
    cin.rdbuf(in.rdbuf());

ll ar[550][550];
ll rows[550][550];
ll diagonals[550][550];
ll diagonals2[550][550];
ll n, m, k;


ll getVal(ll y, ll x)
{
    if (y < 0 || x < 0)
        return 0;
    return rows[y][x];
}
ll alasKolmio(ll y, ll x, ll k)
{
    ll sumRowSmallerX = y % 2 == 1 ? x - 1 - 1 : x - 1;
    ll sumRowSmallerY = y - 1;
    ll rowSumSmaller = getVal(sumRowSmallerY, sumRowSmallerX);

    ll sumRowLargerX = y % 2 == 1 ? (x - 1 + k - 1) : (x + k - 1);
    ll sumRowLargerY = y - 1;
    ll rowSumLarger = getVal(sumRowLargerY, sumRowLargerX);

    ll minDiagonalX = x + k - 1 + (y % 2 == 0 ? 1 : 0);
    ll minDiagonalY = y - 1;
    ll diagonalSmaller = diagonals2[minDiagonalY][minDiagonalX];

    ll maxDiagonalX = x + (y % 2 == 1 ? (k / 2 - 1 + k % 2) : (k / 2));
    ll maxDiagonalY = y + k - 1;
    ll diagonalLarger = diagonals2[maxDiagonalY][maxDiagonalX];

    ll result = (diagonalLarger - diagonalSmaller) - (rowSumLarger - rowSumSmaller);
    return result;
}
ll ylosKolmio(ll y, ll x, ll k)
{
    ll rowSumSmaller = rows[y][x - 1];
    ll rowSumLarger = rows[y][x + k - 1];
    bool parillinen = (y % 2 == 0);
    ll minDiagonalX = x + (parillinen ? (k / 2) : (k / 2 - 1 + k % 2));
    ll diagonalSmaller = y - k - 1 < 0 ? 0 : diagonals2[y - k - 1][minDiagonalX];
    ll diagonalLarger = diagonals2[y - 1][x + (parillinen ? 0 : -1)];

    ll result = (rowSumLarger - rowSumSmaller) - (diagonalLarger - diagonalSmaller);

    return result;
}

ll main()
{
    cin >> n >> m >> k;
    ll kokonaismaara = 0;
    for (ll i = 0; i < k; i++)
    {
        ll a, b;
        char c;
        cin >> a >> b >> c;

        ar[a][b] = c == 'K' ? -10 : 1;
        kokonaismaara += ar[a][b];
    }
    ll L = 520;
    // down left-right
    for (ll sy = 1; sy <= L; sy += 2)
    {
        ll summa = 0;
        ll x = 0;
        for (ll y = sy; y <= L; y++)
        {
            if (y % 2 == 1)
                x++;
            summa += ar[y][x];
            diagonals[y][x] = summa;
        }
    }
    // right left-right
    for (ll sx = 1; sx <= L; sx++)
    {
        ll summa = 0;
        ll x = sx;
        for (ll y = 1; y <= L; y++)
        {
            if (y % 2 == 1)
                x++;
            if (y >= 550 || x >= 550)
                continue;
            summa += ar[y][x];
            diagonals[y][x] = summa;
        }
    }
    // right right-left
    for (ll sx = 1; sx <= L; sx++)
    {
        ll x = sx;
        ll summa = 0;
        for (ll y = 1; y <= L; y++)
        {
            if (y % 2 == 0)
                x--;
            if (x < 0 || y < 0)
                continue;
            summa += diagonals[y][x];
            diagonals2[y][x] = summa;
        }
    }

    // rows
    for (ll y = 0; y <= L; y++)
    {
        ll summa = 0;
        for (ll x = 0; x <= L; x++)
        {
            summa += diagonals[y][x];
            rows[y][x] = summa;
        }
    }
    // System.out.prllln("Preparing done " + n + " " + m);
    // prll();
    ll minSum = 999999999;
    for (ll y = 1; y <= n; y++)
    {
        // System.out.prllln("Y" + y);
        for (ll x = 1; x <= m; x++)
        {
            // down
            ll maxKDown = m + 1 - x;
            maxKDown = min(maxKDown, n + 1 - y);
            // up
            ll maxKUp = m + 1 - x;
            maxKUp = min(maxKUp, y);

            ll maxK = max(maxKDown, maxKUp);
            for (ll k = 1; k <= maxK; k++)
            {
                ll result;
                ll oikeaArvo;

                if (k <= maxKDown)
                {
                    result = k == 1 ? ar[y][x] : alasKolmio(y, x, k);
                    minSum = min(minSum, result);
                }
                if (k <= maxKUp)
                {
                    result = k == 1 ? ar[y][x] : ylosKolmio(y, x, k);
                    minSum = min(minSum, result);
                }

            }
        }
    }
    cout << (kokonaismaara - minSum);
}