Codeforces Round #703 (div.2)

Codeforces Round #703 (div.2)

---

A. Shifting Stacks

(solved)

 Problem 

Problem - A - Codeforces

 Code 

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
typedef unsigned long long ull;
 
int tc;
vector<ull> dp(101, 0);
vector<string> ans;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 1; i <= 100; i++) {
        dp[i] = i + dp[i - 1];
    } // dp[i] : i'th stack 까지 strictly increasing
    //   하기 위한 blocks 들의 최소 개수.
 
    cin >> tc;
    ans.resize(tc, " ");
 
    for (int c = 0; c < tc; c++) {
        int n;
        cin >> n;
 
        vector<ull> stacks(n);
        vector<ull> sum(n, 0);
 
        for (int i = 0; i < n; i++) {
            cin >> stacks[i];
 
            if (i) {
                sum[i] = stacks[i] + sum[i - 1];
 
                if (sum[i] < dp[i]) ans[c] = "NO";
            }
            else sum[i] = stacks[i];
 
            if (i == n - 1 && ans[c] == " ") ans[c] = "YES";
        }
    }
 
    for (auto e : ans) cout << e << '\n';
}

 How to solve 

  먼저, #17 ~ #19 line 에서 dp[ i ] 에 stacks[ i ] 까지 strictly increasing 하기 위한 block들의 최소 개수를 memoization 해 놓았다. 그리고 stacks[ i ] 를 하나 하나 받으면서 sum[ i ] 에 #35 ~ #40 line 에서와 같이 현재 입력된 i 번째 stacks 까지의 블록의 합을 입력하였다. 그리고 #38 에서 만약 i 번째 까지의 block의 합이 dp[ i ] ( i 번째 stacks 까지 strictly increasing 하기 위한 block의 최소 개수보다 작으면 ans[ c ] 의 값을 "NO" 로 변경해 주었다. 그리고 #42 line 에선 만약 i 가 for 문의 끝까지 왔는데 아직 ans[ c ] 에 답이 입력되지 않았으면, 지금껏 "NO" 인 상황이 없던 것 이므로 "YES"를 입력해 주었다.