fork download
copy 
  1. /* Author : Nguyen Thanh Tung - Tran Hung Dao High School for Gifted Student */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define endl 		     '\n'
  6. #define int 		     long long
  7.  
  8. using namespace 	     std;
  9.  
  10. typedef pair<int, int> ii;
  11.  
  12. const int       N      = 1e5 + 7;
  13. const long long oo     = 1e18 + 7;
  14. const long long MOD    = 1e9 + 7;
  15.  
  16. int n, a[N], b[N], dp[N];
  17.  
  18. void solve() {
  19.    cin >> n;
  20.    for(int i = 1; i <= n; ++i) {
  21.       cin >> a[i] >> b[i];
  22.    }
  23.    dp[n] = a[n];
  24.    for(int i = n - 1; i >= 1; --i) {
  25.       dp[i] = min(dp[i + 1] + a[i], dp[i + 2] + b[i]);
  26.    }
  27.    cout << dp[1] << endl;
  28.    for(int i = 1; i <= n; ++i) {
  29.       if(dp[i] == dp[i + 1] + a[i]) {
  30.          cout << "1 ";
  31.       }
  32.       else {
  33.          cout << "2 0 ";
  34.          ++i;
  35.       }
  36.    }
  37. }
  38.  
  39. signed main () {
  40.    ios_base::sync_with_stdio (false);
  41.    cin.tie(nullptr), cout.tie(nullptr);
  42.  
  43.    #define TASK "riceatm"
  44.    if (fopen(TASK".INP", "r")) {
  45.       freopen(TASK".INP", "r", stdin);
  46.       freopen(TASK".OUT", "w", stdout);
  47.    }
  48.  
  49.    solve();
  50.    return 0;
  51. }
  52.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Gztt8C
language:
C++14 (clang 8.0)
created:
1 day 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!