---
# System prepended metadata

title: Solution Mely Edu Contest 4 - C. Projects

---


## Solution Mely Edu Contest 4 - C. Projects

###### 📋 Content: 
[TOC]
____
### Nhận xét :label:
- Đầu tiên ta cần sắp xếp các dự án lại theo thời gian kết thúc tăng dần.
- Gọi $dp[i]$ là số tiền tối đa đạt được sau khi dự án thứ $i$ kết thúc, bất kể việc có chọn làm hay không dự án $i$. ($i$ sau khi đã sắp xếp)
- Tại mỗi dự án đang xét, ta chỉ quan tâm dự án có nên chọn hay không bằng việc so sánh:
    - Nếu như chọn, ta quan tâm số tiền lớn nhất có thể đạt được trước khi gia nhập dự án này, cộng với số tiền của dự án đang xét. 
    - Nếu như không chọn, ta giữ nguyên số tiền lớn nhất khi kết thúc dự án trước đó.
- Như vậy ta có công thức dp như sau:
$$dp[i] = max(dp[i-1],dp[x] + value[i])$$
:::info
- Lưu ý: $x$ là số lớn nhất sao cho thời gian kết thúc của dự án thứ $x$ không lớn hơn thời gian bắt đầu của dự án thứ $i$. Việc tính giá trị $x$ chỉ đơn giản là chặt nhị phân để tìm kiếm.
- $value[i]$ là số tiền nhận được nếu hoàn thành dự án $i$
:::
### Code
> **Time:** $O(n^{2})$
> **Space:** $O(n^2)$ 
> **Algo:** Dynamic programing.
> [color=lightgreen] 
:::success
:::spoiler Code
```cpp= 
#include <bits/stdc++.h>
 
#define ll long long
#define endl "\n"
#define afor(i,n) for(int i =0; i<n;i++)
#define push_back emplace_back
//priority_queue <int> ; less
//priority_queue <int,vector<int>,greater<int> > ; greater
 
using namespace std;
 
map<ll,int> lt;
struct prjct
{
    ll a,b,c;
    bool operator<(const prjct &p){
        return b<p.b;
    }
};
prjct arr[200005];
ll dp[200005];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    for (int i =0; i<n;i++){
        cin>>arr[i].a>>arr[i].b>>arr[i].c;
        lt[arr[i].b]=0;
    }
    lt[0]=0;
    sort(arr,arr+n);
    int k=0;
    map<ll,int>::iterator it;
    for (it=lt.begin(); it!=lt.end(); it++){
        it->second=k;
        k++;
    }
    dp[0]=0;
    k--;
    ll res=0;
    for (int i =0; i<n;i++){
        it=--lt.lower_bound(arr[i].a);
        int ii=lt[arr[i].b];
        dp[ii]=max({dp[ii],dp[it->second]+arr[i].c,dp[ii-1]});
        res=max(res,dp[ii]);
    }
    cout<<res<<endl;
    return 0;
}
```
:::