ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1119. Метро

С++14 AC
Послано D4nick 27 янв 2019 01:07
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001][1001];
bool Diag[1001][1001];
int main() {
    int maxX, maxY, K, X, Y;
    cin >> maxX >> maxY >> K;
    for (int i = 0; i < K; i++) {
        cin >> X >> Y;
        Diag[X][Y] = true;
    }
    for (int x = 1; x <= maxX; ++x)
        for (int y = 1; y <= maxY; ++y)
             dp[x][y] = max(max(dp[x - 1][y], dp[x][y - 1]), dp[x - 1][y - 1] + int(Diag[x][y]));
    int maxKolD = dp[maxX][maxY];
    cout << round(maxKolD*sqrt(20000) + (maxX - maxKolD) * 100 + (maxY - maxKolD) * 100);
}