Submission #502977

#	Time	Username	Problem	Language	Result	Execution time	Memory
502977		Kirill_Maglysh	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	1 ms	332 KiB

dango_maker

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

#define fori(n) for(int i = 0; i < n; ++i)
#define forj(n) for(int j = 0; j < n; ++j)
#define forr(n) for(int i = n - 1; i >= 0; --i)
#define forEach(array) for(auto &item : array)
#define printSpace(a) cout << a << " "
#define printSpace2(a, b) cout << a << " " << b << " "
#define printSpace3(a, b, c) cout << a << " " << b << " " << c << " "
#define printSpace4(a, b, c, d) cout << a << " " << b << " " << c << " " << d <<" "
#define printSpace5(a, b, c, d, e) cout << a << " "<< b << " " << c << " " << d <<" " << e << " "
#define printSpace6(a, b, c, d, e, f) cout << a << " "<< b << " " << c << " " << d <<" "<< e << " " << f << " "
#define printLn(n) cout << n << '\n'
#define printNL() cout <<'\n'
#define print(n) cout << n

using namespace std;

typedef long long ll;

struct CompressedLetter {
    ll num;
    char letter;
};

ll readLL();

string readStr();

void resolve();

void resolveTest();

bool isPrime(ll n);

vector<bool> detectPrimes(ll n);

ll minPosInArray(const vector<ll> &nums);

ll maxPosInArray(const vector<ll> &nums);

ll minValInArray(const vector<ll> &nums);

ll maxValInArray(const vector<ll> &nums);

vector<ll> calcPrefixSum(const vector<ll> &nums);

vector<ll> calcSuffixSum(const vector<ll> &nums);

vector<ll> getDigits(ll n);

ll sumNumRange(ll start, ll finish);

ll calcNumLength(ll n);

vector<CompressedLetter> processCompressedStr(const string &str);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    resolve();

    return 0;
}


char field[3009][3009];
ll dp[3009][3009][4];

bool check(ll x, ll y) {
    return ((field[x][y] == 'G') && (field[x - 1][y] == 'R') && (field[x + 1][y] == 'W'));
}

bool check2(ll x, ll y) {
    return ((field[x][y] == 'G') && (field[x][y - 1] == 'R') && (field[x][y + 1] == 'W'));
}

void resolve() {
    ll n = readLL();
    ll m = readLL();
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            cin >> field[i][j];
        }
    }
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j + 1][0]);
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j + 1][1]);
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j + 1][2]);
            if (check(i, j)) {
                dp[i][j][1] = max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + 1;
            }
            if (check2(i, j)) {
                dp[i][j][2] = max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][2]) + 1;
            }
        }
    }

    ll res = 0;
    for (ll i = 1; i <= n; i++) {
        res += max({dp[i][1][0], dp[i][1][1], dp[i][1][2]});
    }
    for (ll i = 2; i <= n; i++) {
        res += max({dp[n][i][0], dp[n][i][1], dp[n][i][2]});
    }

    printLn(res);
}

ll readLL() {
    ll num;
    cin >> num;
    return num;
}

string readStr() {
    string str;
    cin >> str;
    return str;
}

bool isPrime(ll n) {
    if (n == 0 || n == 1) {
        return false;
    }

    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

vector<bool> detectPrimes(ll n) {
    vector<bool> nums(n + 1, true);
    nums[0] = false;
    nums[1] = false;
    for (ll i = 2; i <= n; ++i) {
        if (nums[i]) {
            for (ll j = i * i; j <= n; j += i) {
                nums[j] = false;
            }
        }
    }

    return nums;
}

ll minPosInArray(const vector<ll> &nums) {
    ll pos = 0;
    for (ll i = 1; i < nums.size(); ++i) {
        if (nums[pos] > nums[i]) {
            pos = i;
        }
    }

    return pos;
}

ll maxPosInArray(const vector<ll> &nums) {
    ll pos = 0;
    for (ll i = 1; i < nums.size(); ++i) {
        if (nums[pos] < nums[i]) {
            pos = i;
        }
    }

    return pos;
}

vector<ll> getDigits(ll n) {
    vector<ll> digits;
    while (n > 0) {
        digits.push_back(n % 10);
        n /= 10;
    }

    return digits;
}

vector<ll> calcPrefixSum(const vector<ll> &nums) {
    vector<ll> prefix(nums.size());
    prefix[0] = nums[0];
    for (ll i = 1; i < nums.size(); ++i) {
        prefix[i] = prefix[i - 1] + nums[i];
    }

    return prefix;
}

vector<ll> calcSuffixSum(const vector<ll> &nums) {
    vector<ll> suffix(nums.size());
    suffix[nums.size() - 1] = nums[nums.size() - 1];
    for (ll i = (ll) nums.size() - 2; i >= 0; --i) {
        suffix[i] = suffix[i + 1] + nums[i];
    }

    return suffix;
}

ll sumNumRange(ll start, ll finish) {
    if (finish < start) {
        return 0;
    }

    if (start > 1) {
        return sumNumRange(1, finish) - sumNumRange(1, start - 1);
    }

    if (finish % 2 == 1L) {
        return sumNumRange(1, finish - 1) + finish;
    } else {
        return finish * (finish + 1) / 2;
    }
}

vector<CompressedLetter> processCompressedStr(const string &str) {
    vector<CompressedLetter> res;
    ll pos = 0;

    while (pos < str.length()) {
        ll numLength = 0;
        while ('0' <= str[pos] && str[pos] <= '9') {
            numLength++;
            pos++;
        }

        if (numLength == 0) {
            res.push_back({1, str[pos]});
        } else {
            res.push_back({stoi(str.substr(pos, numLength)), str[pos + numLength]});
        }

        pos += numLength + 1;
    }

    return res;
}

ll calcNumLength(ll n) {
    ll res = 0;
    while (n > 0) {
        n /= 10;
        res++;
    }

    return res;
}

ll minValInArray(const vector<ll> &nums) {
    return nums[minPosInArray(nums)];
}

ll maxValInArray(const vector<ll> &nums) {
    return nums[maxPosInArray(nums)];
}

Compilation message (stderr)

dango_maker.cpp: In function 'll minPosInArray(const std::vector<long long int>&)':
dango_maker.cpp:159:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for (ll i = 1; i < nums.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
dango_maker.cpp: In function 'll maxPosInArray(const std::vector<long long int>&)':
dango_maker.cpp:170:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     for (ll i = 1; i < nums.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
dango_maker.cpp: In function 'std::vector<long long int> calcPrefixSum(const std::vector<long long int>&)':
dango_maker.cpp:192:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |     for (ll i = 1; i < nums.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
dango_maker.cpp: In function 'std::vector<CompressedLetter> processCompressedStr(const string&)':
dango_maker.cpp:229:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     while (pos < str.length()) {
      |            ~~~~^~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67