Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
// Problema Superhedgy, OJI XI 2022 // Solutie in O(totalL) - 80p #include
using namespace std; ifstream cin("superhedgy.in"); ofstream cout("superhedgy.out"); typedef long long ll; const int mxN = 1e5; // hA[i] - heightA[i] - inaltimea cladirii in sus a pozitiei (i-1,i); // eA[i] - efortA[i] - costul liftului de sus pana la nivelul solului in poz (i-1,i); ll hA[mxN+10],hB[mxN+10], eA[mxN+10],eB[mxN+10]; /* 1. Definitia : dp[0][i] - distanta minima parcursa pe verticala pentru a ajunge pana in punctul (i, hA[i]); dp[1][i] - la fel dar pentru a ajunge in punctul (i,hB[i]) */ ll dp[2][mxN+10]; int main() { // Citirea datelor int n, m, totalL = 0; cin >> n ; for(int i = 1;i<=n;i++) { ll L, H, E; cin >> L >> H >> E; while(L--) { totalL++; hA[totalL] = H; eA[totalL] = E; } } cin >> m; totalL = 0; for(int i = 1;i<=m;i++) { ll L, H, E; cin >> L >> H >> E; while(L--) { totalL++; hB[totalL] = H; eB[totalL] = E; } } // 2. Cazuri de baza : dp[0][1] si dp[1][1] dp[0][1] = min(hA[1], hB[1] + eA[1] + eB[1]); dp[1][1] = min(hB[1], hA[1] + eA[1] + eB[1]); // 3. Tranzitii pentru dp[0][i] , dp[1][i], unde 2<=i<=totalL for(int i = 2;i<=totalL;i++) { dp[0][i] = dp[0][i-1] + abs(hA[i-1] - hA[i]); dp[1][i] = dp[1][i-1] + abs(hB[i-1] - hB[i]); dp[0][i] = min(dp[0][i], dp[1][i] + eA[i] + eB[i]); dp[1][i] = min(dp[1][i], dp[0][i] + eA[i] + eB[i]); } /* 4. Raspunsul este distanta minima parcursa pe orizontala + dist minim parcursa pe verticala. Distanta minima pe orizontala mereu este totalL, iar distanta parcursa pe verticala va fi minimul dintre distanta parcursa pentru a ajunge in punctul (totalL,hA[totalL]) + inaltimea parcursa pt a cobori jos la punctul (totalL,0); sau distanta parcursa pt a ajunge in punctul (totalL,hB[totalL]) + inaltimea pt a urca in sus pana la punctul (totalL,0); */ cout << totalL + min(dp[0][totalL] + hA[totalL], dp[1][totalL] + hB[totalL]); return 0; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)