# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
289564 | TadijaSebez | Treatment Project (JOI20_treatment) | C++11 | 3077 ms | 2680 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];
int n,m;
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){
if(r==n)return 0;
if(b.r==n)return 1;
return r+l<b.r+b.l;
}
}pro[N];
int main(){
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;
/*bool ok=0;
if(pro[i].t<pro[j].t){
int l=pro[i].l+(pro[j].t-pro[i].t);
if(l<=pro[j].r+1)ok=1;
}else{
int r=pro[j].r-(pro[i].t-pro[j].t);
if(r>=pro[i].l-1)ok=1;
}
if(ok)*/
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... |