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

Обсуждение задачи 1203. Научная конференция

I am getting a tle on my dp algo ontest case !11
Послано suryansh 21 июн 2016 10:28
#include "bits/stdc++.h"
using namespace std;
vector<pair<int,int> > v;
int n;
vector<int> v1;
int dp[100001];
int recurse(int temp){

    if(dp[temp] != -1)
        return dp[temp];

    int search = v[temp].second;
    int lower = lower_bound(v1.begin(), v1.end(), search) - v1.begin();
    // cout << search << " " << lower << "**";
    int max1 = 0;
    for(int i = lower; i < v1.size(); i++){
        // cout << v1[i] << "/" << search << "\n";
        if(v1[i] - search >= 1){
            max1 = max(max1, recurse(i)+1);
        }
    }
    return dp[temp] = max1;
}
int main(int argc, char const *argv[])
{
    // ios::sync_with_stdio(false);
    scanf("%d",&n);
    memset(dp, -1, sizeof dp);
    while(n--){
        int st, en;
        scanf("%d%d",&st,&en);
        v.push_back(make_pair(st, en));
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++){
        v1.push_back(v[i].first);
        // cout << v[i].first << " " << v[i].second << "\n";
    }
    int max1 = 0;
    for(int i  = 0; i < v.size(); i++)
        max1 = max(max1, recurse(i)+1);
    printf("%d",max1);
    return 0;
}