Submission #1205305

#TimeUsernameProblemLanguageResultExecution timeMemory
1205305mychecksedadTreatment Project (JOI20_treatment)C++20
0 / 100
3094 ms4224 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; const ll INF = 1e18; int n, m; array<ll, 4> a[N]; ll dp[N]; void solve(){ cin >> n >> m; for(int i = 1; i <= m; ++i){ cin >> a[i][2] >> a[i][0] >> a[i][1] >> a[i][3]; } sort(a+1, a+1+m); ll ans = INF; for(int i = 1; i <= m; ++i){ if(a[i][0] == 1){ dp[i] = a[i][3]; }else{ dp[i] = INF; for(int j = 1; j < i; ++j){ if(a[j][1] >= a[i][0] - 1){ ll t1 = a[j][2]; ll t2 = a[i][2]; if(abs(t1-t2) <= a[j][1] - a[i][0] + 1){ dp[i] = min(dp[i], dp[j] + a[i][3]); } } } if(a[i][1] == n){ ans = min(ans, dp[i]); } } // cerr << a[i][0] << ' ' << a[i][1] << ' '; // cerr << i << ' ' << dp[i] << '\n'; } if(ans==INF){ cout << -1; }else{ cout<< ans; } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...