Submission #570113


Source Code Expand

Copy
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
  int N;
  long long K;
  scanf("%d%lld", &N, &K);
  vector<long long> A(N+1);
  for(int i = 0; i < N; ++i) {
    scanf("%lld", &A[i]);
    --A[i];
  }
  long long current_count = -1;
  {
    long long current_height = 0;
    for(long long x : A) {
      current_count += abs<long long>(current_height - x);
      current_count += 3 + 2 * x;
      current_height = x;
    }
  }
  A[N] = 0;
  vector<pair<long long,int>> st; st.reserve(N+2);
  vector<pair<int,long long>> parts; parts.reserve(N+2);
  st.emplace_back(0, 0);
  for(int i = 0; i <= N; ++i) {
    while(st.back().first > A[i]) {
      auto x = st.back(); st.pop_back();
      parts.emplace_back(x.second, x.first-max<long long>(A[i], st.back().first));
      if(st.back().first >= A[i]) {
        st.back().second += x.second;
      } else {
        st.emplace_back(A[i], x.second);
      }
    }
    if(st.back().first == A[i]) {
      st.back().second += 1;
    } else {
      st.emplace_back(A[i], 1);
    }
  }
  sort(parts.begin(), parts.end());
  long long Krem = K;
  for(auto part : parts) {
    if(Krem >= part.first * part.second) {
      // fprintf(stderr, "consume: %d * %lld\n", part.first, part.second);
      current_count -= (part.first * 2 + 2) * part.second;
      Krem -= part.first * part.second;
    } else {
      long long consum1 = Krem / part.first;
      // fprintf(stderr, "consume: %d * %lld\n", part.first, consum1);
      current_count -= (part.first * 2 + 2) * consum1;
      Krem -= part.first * consum1;
      // fprintf(stderr, "consume: (%d)\n", (int)Krem);
      current_count -= (Krem * 2);
      Krem = 0;
      break;
    }
  }
  printf("%lld\n", current_count);
  return 0;
}

Submission Info

Submission Time
Task B - 立方体とペンキ
User qnighy
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1834 Byte
Status
Exec Time 67 ms
Memory 4652 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:9:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld", &N, &K);
                          ^
./Main.cpp:12:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &A[i]);
                         ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt
All 100 / 100 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt
Case Name Status Exec Time Memory
01-01.txt 30 ms 708 KB
01-02.txt 26 ms 800 KB
01-03.txt 67 ms 3112 KB
01-04.txt 67 ms 3104 KB
01-05.txt 66 ms 3108 KB
01-06.txt 66 ms 3096 KB
01-07.txt 67 ms 3108 KB
01-08.txt 48 ms 1688 KB
01-09.txt 50 ms 1568 KB
01-10.txt 48 ms 1696 KB
01-11.txt 50 ms 1692 KB
01-12.txt 60 ms 4648 KB
01-13.txt 59 ms 4652 KB
01-14.txt 56 ms 3108 KB
01-15.txt 55 ms 3100 KB
01-16.txt 57 ms 3876 KB
01-17.txt 58 ms 3872 KB
sample-01.txt 27 ms 800 KB
sample-02.txt 25 ms 792 KB