제출 #40728

#제출 시각아이디문제언어결과실행 시간메모리
40728bogdan10bosSkyscraper (JOI16_skyscraper)C++14
100 / 100
159 ms18628 KiB
#include <bits/stdc++.h> using namespace std; //#define FILE_IO const int mod = 1e9 + 7; typedef pair<int, int> pii; typedef pair<pii, pii> p4i; int N, L; int v[105]; int dp[105][105][1005][3]; bool inq[105][105][1005][3]; /// dp[i][j][k][e] - first i numbers, j remaining gaps, k cost, e ends are fixed queue<p4i> q; void addto(int x, int y, int z, int e, int vl) { if(x == 3 && y == 1 && z == 4 && e == 1) { x++; x--; } if(x < 0 || y < 0 || z < 0 || e < 0) return; if(z > L) return; if(vl == 0) return; if(y == 1 && e == 0) return; if(y == 0 && e <= 1) return; if(x != N && y == 0) return; if(y > N - x) return; dp[x][y][z][e] += vl; if(dp[x][y][z][e] >= mod) dp[x][y][z][e] -= mod; if(!inq[x][y][z][e]) { q.push( { {x, y}, {z, e} } ); inq[x][y][z][e] = 1; } } void brute(int v[]) { vector<int> p; for(int i = 1; i <= N; i++) p.push_back(v[i]); vector< vector<int> > pp[105]; sort(p.begin(), p.end()); int ans = 0; do { int cnt = 0; for(int i = 1; i < p.size(); i++) cnt += abs(p[i] - p[i - 1]); if(cnt <= L) ans++; }while(next_permutation(p.begin(), p.end())); printf("%d\n", ans); } int main() { #ifdef FILE_IO freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif scanf("%d%d", &N, &L); if(N == 1) { printf("1\n"); exit(0); } for(int i = 1; i <= N; i++) scanf("%d", &v[i]); sort(v + 1, v + N + 1); /*if(N <= 8) { brute(v); exit(0); }*/ dp[1][2][0][0] = 1; q.push({ {1, 2}, {0, 0} }); dp[1][1][0][1] = 2; q.push({ {1, 1}, {0, 1} }); int ans = 0; while(!q.empty()) { auto x = q.front(); q.pop(); int i = x.first.first; int j = x.first.second; int k = x.second.first; int e = x.second.second; int nk = k + (v[i + 1] - v[i]) * (2 * j - 2 + e); int vl = dp[i][j][k][e]; if(nk > L) continue; if(i == N) { if(j == 0 && e == 2 && k <= L) (ans += dp[i][j][k][e]) %= mod; continue; } /// middle, no fix addto(i + 1, j + 1, nk, e, (1LL * vl * j) % mod); /// middle, 1 fix, 1 free addto(i + 1, j, nk, e, (1LL * vl * (j * 2 - 2 + e)) % mod); /// middle, 2 fix addto(i + 1, j - 1, nk, e, (1LL * vl * (j - 2 + e)) % mod); if(e == 0) { /// end, no fix addto(i + 1, j, nk, e + 1, (2 * vl) % mod); /// end, fix addto(i + 1, j - 1, nk, e + 1, (2 * vl) % mod); } else if(e == 1) { /// end, no fix addto(i + 1, j, nk, e + 1, vl); /// end, fix addto(i + 1, j - 1, nk, e + 1, vl); } } printf("%d\n", ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'void brute(int*)':
skyscraper.cpp:57:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < p.size(); i++)
                          ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:71:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &L);
                          ^
skyscraper.cpp:77:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d", &v[i]);
                                                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...