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

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

O(k^2) dp solution
Послано lnxdx 4 авг 2019 00:22
// ITNOA
// O(k^2) dp by lnxdx, Mashhad, 2019
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
pair<int, int>a[N];
int dp[N];
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0;i < k;i++)
        cin >> a[i].first >> a[i].second;

    sort(a, a + k);
    int lis = 0;
    for (int i = 0;i < k;i++)
    {
        dp[i] = 1;
        for (int j = 0;j < i && a[j].first < a[i].first;j++)
            if (a[j].second < a[i].second)
                dp[i] = max(dp[i], dp[j] + 1);
        lis = max(lis, dp[i]);
    }
    double ans = 100 * ((m - lis) + (n - lis) + sqrt(2)*lis);
    cout << round(ans);
}