You are not logged in. Please login at www.codechef.com to post your questions!

×

ZCO Little Red Riding Hood - Error in 1 test case

I am solving the ZCO Contest - Little Red Riding Hood problem. The code I've written works correctly for all test cases except one - the case no. 6. I am not able to realize the error.

My approach is a simple DP approach.

Please help in debugging my code.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

// ZCO13002 ZCO13002 ZCO13002 ZCO13002 ZCO13002 ZCO13002

int main() {
    long long side, protections, number;
    cin >> side >> protections;

    pair<bool, long> array[500][500];

    for (long i = 0; i < side; i++) {
        for (long j = 0; j < side; j++) {
            cin >> number;
            array[i][j] = make_pair(false, number);
        }
    }

    long long x, y, strength, top, left, zero = 0;
    for (long i = 0; i < protections; i++) {
        cin >> x >> y >> strength;
        x--;
        y--;

        for (long i = max(x - strength, zero); i <= min(side-1, x+strength); i++) {
            for (long j = max(y - strength, zero); j <= min(side-1, y+strength); j++) {
                if (abs(x-i) + abs(y-j) <= strength) array[i][j].first = true;
            }
        }
    }

    for (long i = 0; i < side; i++) {
        for (long j = 0; j < side; j++) {
            if (array[i][j].first && (i > 0 && !(array[i-1][j].first)) && (j > 0 && !(array[i][j-1].first))) {
                array[i][j] = make_pair(false, array[i][j].second);
            }

            if (array[i][j].first) {
                if (i > 0 && array[i-1][j].first) top = array[i-1][j].second;
                else top = -1001 * 1001;

                if (j > 0 && array[i][j-1].first) left = array[i][j-1].second;
                else left = -1001 * 1001;

                if (i == 0 && j == 0) top = 0;

                array[i][j] = make_pair(true, max(top, left) + array[i][j].second);
            }
        }
    }

    /*
    for (int i = 0; i < side; i++) {
        for (int j = 0; j < side; j++) {
            if (array[i][j].first) cout << "1 ";
            else cout << "0 ";
        }
        cout << endl;
    }
    */

    if (array[side-1][side-1].first) cout << "YES\n" << array[side-1][side-1].second;
    else cout << "NO\n";

    return 0;
}

Please help. Thanks.

asked 06 Jul '17, 16:07

dhruvsomani's gravatar image

4★dhruvsomani
1448
accept rate: 8%

edited 07 Jul '17, 19:02

Please help me with this one.

(21 Jul '17, 16:02) dhruvsomani4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,211
×427
×365
×56
×25

question asked: 06 Jul '17, 16:07

question was seen: 340 times

last updated: 21 Jul '17, 16:02