Submission #1193153

#TimeUsernameProblemLanguageResultExecution timeMemory
1193153Fikrat_AsadzadehSkyscraper (JOI16_skyscraper)C++20
0 / 100
1 ms584 KiB
#include <bits/stdc++.h> using namespace std; const int MOD = 1'000'000'007; static int dp[105][105][1005]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, L; cin >> N >> L; vector<int> A(N); for(int i = 0; i < N; i++) cin >> A[i]; sort(A.begin(), A.end()); vector<int> D(N); for(int i = 0; i + 1 < N; i++) D[i] = A[i+1] - A[i]; dp[1][1][0] = 1; int minimal = 0; for(int i = 0; i + 1 < N; i++) minimal += D[i]; for(int i = 1; i < N; i++){ for(int k = 1; k <= i; k++){ for(int s = 0; s <= L; s++){ int ways = dp[i][k][s]; if(!ways) continue; dp[i+1][k+1][s] = (dp[i+1][k+1][s] + ways) % MOD; int ns = s + k * D[i]; if(ns <= L){ dp[i+1][k][ns] = (dp[i+1][k][ns] + ways) % MOD; } } } } int ans = 0; for(int s = 0; s <= L; s++){ if(minimal + 2*s <= L){ ans = (ans + dp[N][1][s]) % MOD; } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...