oj.uz

답안 #375468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375468 2021-03-09T12:51:49 Z spatarel Skyscraper (JOI16_skyscraper) C++17
15 / 100
 2 ms 1004 KB 
#include <stdio.h>
#include <algorithm>
 
const int MOD = 1'000'000'007;
 
const int MAX_N = 100;
const int MAX_L = 1000;
 
long long Count[2][1 + MAX_N + 1][1 + MAX_L][1 + 2 + 1];
 
void addSelf(long long &a, long long b) {
  a = (a + b) % MOD;
}

void myAssert(bool eval) {
  if (!eval)
    for (;;);
}
 
int main() {
  int N, L;
  scanf("%d%d", &N, &L);
  int A[1 + N];
  for (int i = 1; i <= N; i++) {
    scanf("%d", &A[i]);
  }
  std::sort(A + 1, A + N + 1);
  Count[0][0][0][0] = 1;
  for (int i = 0; i + 1 <= N; i++) {
    int I = i % 2;
    int newI = (i + 1) % 2;
    for (int d = 0; d <= N; d++) {
      for (int l = 0; l <= L; l++) {
        for (int e = 0; e <= 2; e++) {
          Count[newI][d][l][e] = 0;
        }
      }
    }
    for (int d = 0; d <= N; d++) {
      for (int l = 0; l <= L; l++) {
        for (int e = 0; e <= 2; e++) {
          int newL = l+(2*d-e)*(A[i+1]-A[i]);
          if (0 <= newL && newL <= L) {
            myAssert(0 <= I && I < 2
                  && 0 <= d && d <= MAX_N + 1
                  && 0 <= l && l <= MAX_L
                  && 0 <= e && e <= 2 + 1);
            myAssert(0 <= newI && newI < 2
                  && 0 <= d + 1 && d + 1 <= MAX_N + 1
                  && 0 <= newL && newL <= MAX_L
                  && 0 <= e + 1 && e + 1 <= 2 + 1);
            addSelf(Count[newI][d + 1][newL][e]    , (d+1-e) * Count[I][d][l][e]); // valley
            if (0 <= d - 1) {
            addSelf(Count[newI][d - 1][newL][e]    , (d-1)   * Count[I][d][l][e]); // peak
            }
            addSelf(Count[newI][d + 0][newL][e]    , (2*d-e) * Count[I][d][l][e]); // edge
            addSelf(Count[newI][d + 0][newL][e + 1], (2-e)   * Count[I][d][l][e]); // edge ending
            addSelf(Count[newI][d + 1][newL][e + 1], (2-e)   * Count[I][d][l][e]); // valley ending
          }
        }
      }
    }
  }
  long long answer = 0;
  for (int l = 0; l <= L; l++) {
    addSelf(answer, Count[N % 2][1][l][2]);
  }
  if (N == 1) {
    answer = 1;
  }
  printf("%lld\n", answer);
  return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |   scanf("%d%d", &N, &L);
      |   ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     scanf("%d", &A[i]);
      |     ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Runtime error 2 ms 1004 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 512 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Runtime error 2 ms 1004 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -