Submission #375462

#TimeUsernameProblemLanguageResultExecution timeMemory
375462spatarelSkyscraper (JOI16_skyscraper)C++17
5 / 100
2 ms876 KiB
#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; } 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) { 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 (stderr)

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