# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
289500 | TadijaSebez | Treatment Project (JOI20_treatment) | C++11 | 3067 ms | 2396 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100050;
const ll inf=9e18;
ll dp[N];
struct project{
int t,l,r,c;
project(){}
project(int a,int b,int d,int e):t(a),l(b),r(d),c(e){}
bool operator < (project b){return r+t<b.r+b.t;}
}pro[N];
int main(){
int n,m;
scanf("%i %i",&n,&m);
for(int i=1;i<=m;i++)scanf("%i %i %i %i",&pro[i].t,&pro[i].l,&pro[i].r,&pro[i].c);
sort(pro+1,pro+1+m);
ll ans=inf;
for(int i=1;i<=m;i++){
if(pro[i].l==1)dp[i]=pro[i].c;
else dp[i]=inf;
for(int j=1;j<i;j++){
int delta_t=abs(pro[i].t-pro[j].t);
if(delta_t>pro[j].r+1-pro[i].l)continue;
dp[i]=min(dp[i],dp[j]+pro[i].c);
}
if(pro[i].r==n)ans=min(ans,dp[i]);
}
printf("%lld\n",ans==inf?-1:ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |