Submission #551780

#TimeUsernameProblemLanguageResultExecution timeMemory
551780Killer2501Skyscraper (JOI16_skyscraper)C++14
100 / 100
1259 ms189436 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define pb push_back #define pll pair<int, pii> #define pii pair<int, int> #define fi first #define se second using namespace std; const int N = 1e2+5; const int M = N*100; const int mod = 1e9+7; const int base = 75; const ll inf = 1e12; int n, t, tong; int k, m, a[N], b[N], dp[N][N][M][3]; int ans, d[N]; void add(int& x, int y) { x += y; if(x >= mod)x -= mod; } void sol() { cin >> n >> k; for(int i = 1; i <= n; i ++)cin >> a[i], b[i] = i; if(n == 1) { cout << 1 << '\n'; return; } sort(a+1, a+1+n); reverse(a+1, a+1+n); dp[1][1][a[1]*2][0] = 1; dp[1][1][a[1]][1] = 2; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= i; j ++) { for(int p = 0; p < M; p ++) { for(int q = 0; q < 3; q ++) { if(dp[i][j][p][q] == 0)continue; if(p+a[i+1]*2 < M)add(dp[i+1][j+1][p+a[i+1]*2][q], 1ll*dp[i][j][p][q]*(j+1-q)%mod); if(q < 2 && p+a[i+1] < M)add(dp[i+1][j+1][p+a[i+1]][q+1], 1ll*dp[i][j][p][q]*(2-q)%mod); add(dp[i+1][j][p][q], 1ll*dp[i][j][p][q]*(2*j-q)%mod); if(q < 2 && p >= a[i+1])add(dp[i+1][j][p-a[i+1]][q+1], 1ll*dp[i][j][p][q]*(2-q)%mod); if(j > 1 && p >= a[i+1]*2)add(dp[i+1][j-1][p-a[i+1]*2][q], 1ll*dp[i][j][p][q]*(j-1)%mod); } } } } for(int i = 0; i <= k; i ++)add(ans, dp[n][1][i][2]); cout << ans << '\n'; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "test" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; //cin >> test; while(test -- > 0)sol(); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:66:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:67:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...