fork(1) download
copy 
  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <iostream>
  7. #include <list>
  8. #include <map>
  9. #include <queue>
  10. #include <set>
  11. #include <stack>
  12. #include <string>
  13. #include <vector>
  14. using namespace std;
  15. typedef unsigned long long llu;
  16. typedef long long ll;
  17. const ll oo = 6666666666;
  18. ll tri[100010][3], dp[100010][3];
  19. int main() {
  20.   int kase = 0, n;
  21.   while (scanf("%d", &n) && n) {
  22.     memset(dp, 0, sizeof(dp));
  23.     memset(tri, 0, sizeof(tri));
  24.     for (int i = 0; i < n; ++i) {
  25.       for (int j = 0; j < 3; ++j) {
  26.         scanf("%lld", &tri[i][j]);
  27.       }
  28.     }
  29.     dp[0][1] = tri[0][1];
  30.     dp[0][2] = dp[0][1] + tri[0][2];
  31.     dp[1][0] = dp[0][1] + tri[1][0];
  32.     dp[1][1] = min(dp[1][0], dp[0][1]) + tri[1][1];
  33.     dp[1][2] = min(min(dp[1][1], dp[0][1]), dp[0][2]) + tri[1][2];
  34.     for (int i = 2; i < n; ++i) {
  35.       dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + tri[i][0];
  36.       dp[i][1] =
  37.           min(min(dp[i - 1][0], dp[i - 1][1]), min(dp[i - 1][2], dp[i][0])) +
  38.           tri[i][1];
  39.       dp[i][2] = min(min(dp[i - 1][1], dp[i - 1][2]), dp[i][1]) + tri[i][2];
  40.     }
  41.     printf("%d. %lld\n", ++kase, dp[n - 1][1]);
  42.   }
  43.   return 0;
  44. }
Success #stdin #stdout 0s 8160KB
comments (?)
stdin
copy 
4
-1 2 3
4 5 6
7 -8 9
-10 2 3
3
-1 2 3
4 5 6
7 -8 9
10
962144 311552 116512 
758155 959008 253152 
400840 351635 191135 
46002 574538 306451 
868013 807917 905506 
245733 25041 978797 
29009 760939 815670 
827196 154487 192891 
610232 464680 338367 
858687 578720 660782 
10
52025 204684 34016 
935715 692264 298955 
893463 685815 445422 
993429 173351 600091 
599342 682834 335887 
385097 41860 965904 
568852 592819 23391 
704495 701855 576817 
469680 856679 978246 
696406 634524 728354 
10
584754 91384 860540 
138460 625334 961002 
176675 659551 827372 
335920 724074 851884 
341357 835899 879596 
704760 160094 834751 
464625 538498 256622 
126352 882078 626405 
645571 789417 280425 
510911 391845 850281 
10
412568 784347 88445 
422148 253784 810872 
714648 51417 227245 
740232 499887 709676 
111996 751367 637155 
367508 857705 32503 
671807 633972 618430 
51180 652468 637560 
589451 946855 868878 
715304 432976 739912 
10
458550 76295 16044 
465552 413242 230316 
806197 582991 983236 
736245 274635 382410 
565389 919603 233562 
653295 845118 774587 
450056 687137 384121 
548694 465007 657741 
801911 878617 823244 
894742 249941 415649 
2
6 4 1 
3 1 7
0
0
stdout
copy 
1. -10
2. -2
3. 2895882
4. 3329609
5. 2799187
6. 3776518
7. 4073366
8. 5
https://ideone.com/ZMvu87
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!