# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
289487 | 2020-09-02T16:59:53 Z | TadijaSebez | Treatment Project (JOI20_treatment) | C++11 | 3000 ms | 2692 KB |
#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 l+r<b.l+b.r||(l+r==b.l+b.r&&t<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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3083 ms | 2692 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Incorrect | 0 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Incorrect | 0 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3083 ms | 2692 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |