Submission #949484

#	Time	Username	Problem	Language	Result	Execution time	Memory
949484		MilosMilutinovic	빌딩 장식 3 (JOI15_building3)	C++14	100 / 100	70 ms	21184 KiB

building3

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> b(n - 1);
  for (int i = 0; i < n - 1; i++) {
    cin >> b[i];
  }
  vector<int> mx(n - 1);
  vector<bool> good(n - 1);
  for (int i = 0; i < n - 1; i++) {
    mx[i] = (i == 0 ? b[i] : max(mx[i - 1], b[i]));
    if (i == 0) {
      good[i] = (b[i] == 1); 
    } else {
      good[i] = (good[i - 1] & (b[i] <= mx[i - 1] + 1));
    }
  }
  long long ans = 0;
  {
    vector<int> seq;
    seq.push_back(1);
    for (int i = 0; i < n - 1; i++) {
      seq.push_back(b[i]);
    }
    bool ok = (seq[0] == 1);
    int mx = 1;
    for (int i = 1; i < n; i++) {
      if (seq[i] > mx + 1) {
        ok = false;
        break;
      }
      mx = max(mx, seq[i]);
    }
    ans += ok;
  }
  set<int> st;
  for (int i = n - 1; i >= 1; i--) {
    if (good[i - 1] && (int) st.size() < 2) {
      if ((int) st.size() == 1) {
        int x = *st.begin();
        if (b[i - 1] != x && x <= mx[i - 1] + 1) {
          ans += 1;
        }
      } else {
        int c = mx[i - 1] + 1;
        if (b[i - 1] <= c) {
          c -= 1;
        }
        ans += c;
      }
    }
    if (i > 1 && b[i - 1] > mx[i - 2] + 1) {
      st.insert(b[i - 1] - 1);
    }
  }
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60