Submission #204198

#TimeUsernameProblemLanguageResultExecution timeMemory
204198AtalasionSkyscraper (JOI16_skyscraper)C++14
15 / 100
11 ms8440 KiB
//khodaya khodet komak kon #include <bits/stdc++.h> #define F first #define S second #define pb push_back #define all(x) x.begin(), x.end() #pragma GCC optimise ("ofast") #pragma GCC optimise("unroll-loops") #define int long long using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; const int N = 100 + 10; const ll MOD = 1000000000 + 7; const ll INF = 1000000000000000000; const ll LOG = 25; int dp[N][1010][N][3], n, a[N], L; int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> L; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); dp[1][0][0][1] = 2; dp[1][0][0][2] = 1; for (int i = 1; i < n; i++) for (int sm = 0; sm <= L; sm++) for (int cnt = 0; cnt <= i + 1; cnt++) for (int cor = 0; cor <= 2; cor++){ if (cnt + cor == 0) continue; int delta = a[i + 1] - a[i]; int num = min(1009* 1ll, sm + (cnt * 2 + cor) * delta); //cout << i << ' ' << sm << ' ' << cnt << ' ' << cor << ' '<< num << ' ' << dp[i][sm][cnt][cor] << '\n'; if (cnt != 0){ dp[i + 1][num][cnt - 1][cor] += cnt * dp[i][sm][cnt][cor]; dp[i + 1][num][cnt - 1][cor] %= MOD; dp[i + 1][num][cnt + 1][cor] += cnt * dp[i][sm][cnt][cor]; dp[i + 1][num][cnt + 1][cor] %= MOD; dp[i + 1][num][cnt][cor] += cnt * 2 * dp[i][sm][cnt][cor]; dp[i + 1][num][cnt][cor] %= MOD; } if (cor != 0){ //cout << "YES" << endl; dp[i + 1][num][cnt + 1][cor - 1] += cor * dp[i][sm][cnt][cor]; dp[i + 1][num][cnt + 1][cor - 1] %= MOD; dp[i + 1][num][cnt + 1][cor] += cor * dp[i][sm][cnt][cor]; dp[i + 1][num][cnt + 1][cor] %= MOD; dp[i + 1][num][cnt][cor - 1] += cor * dp[i][sm][cnt][cor]; dp[i + 1][num][cnt][cor - 1] %= MOD; dp[i + 1][num][cnt][cor] += cor * dp[i][sm][cnt][cor]; dp[i + 1][num][cnt][cor] %= MOD; } } ll ans = 0; for (int i = 0; i <= L; i++) ans += dp[n][i][0][0], ans %= MOD; cout << ans; return 0; }

Compilation message (stderr)

skyscraper.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise ("ofast")
 
skyscraper.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise("unroll-loops")
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...