Submission #1110005

#TimeUsernameProblemLanguageResultExecution timeMemory
1110005InvMODSkyscraper (JOI16_skyscraper)C++14
0 / 100
2 ms2896 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define gcd __gcd #define sz(v) (int) v.size() #define pb push_back #define pi pair<int,int> #define all(v) (v).begin(), (v).end() #define compact(v) (v).erase(unique(all(v)), (v).end()) #define FOR(i, a, b) for(int i = (a); i <= (b); i++) #define dbg(x) "[" #x " = " << (x) << "]" #define int long long using ll = long long; using ld = long double; using ull = unsigned long long; template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;} template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;} const int N = 1e2+5; const int L = 1e3+5; const int mod = 1e9+7; int n, MxL, a[N]; namespace Subtask1{ int answer, vis[10]; vector<int> vec; void backtrack(int pos = 0){ if(pos == n){ int sum = 0; for(int i = 1; i < n; i++){ sum += abs(vec[i] - vec[i-1]); } answer += (sum <= MxL); return; } for(int i = 1; i <= n; ++i){ if(vis[i]) continue; vis[i] = true; vec.pb(a[i]); backtrack(pos+1); vec.pop_back(); vis[i] = false; } return; } void process() { answer = 0; backtrack(); cout << answer <<"\n"; } } namespace Subtask3{ int dp[N][N][L][3]; void process() { // Thanks a Zero_OP <3 // Base case: [0]: just put insert a[1] into an cc, [1]: create new cc that contain endpoint (can locate at first or last) dp[1][1][0][0] = 1; dp[1][1][0][1] = 2; for(int i = 1; i < n; i++){ for(int j = 1; j <= i; j++){ for(int cost = 0; cost <= MxL; cost++){ for(int m = 0; m <= 2; m++){ int nxt_cost = (2*j - m) * (a[i+1] - a[i]); if(nxt_cost > MxL) continue; // Insert a[i] to any exist cc (dp[i+1][j][nxt_cost][m] += dp[i][j][cost][m] * (2*j - m)) %= mod; // Insert a[i] to create endpoint if(m < 2) (dp[i+1][j][nxt_cost][m+1] += dp[i][j][cost][m] * (2 - m)) %= mod; // Insert a[i] to create new cc that does not has endpoint (dp[i+1][j+1][nxt_cost][m] += dp[i][j][cost][m] * (j+1 - m)) %= mod; // Insert a[i] to create new cc with endpoint if(m < 2) (dp[i+1][j+1][nxt_cost][m+1] += dp[i][j][cost][m] * (2 - m)) %= mod; // Merge 2 cc if(j > 1) (dp[i+1][j-1][nxt_cost][m] += dp[i][j][cost][m] * (j-1)) %= mod; } } } } int answer = 0; for(int i = 0; i <= MxL; i++) (answer += dp[n][1][i][2]) %= mod; cout << answer <<"\n"; return; } } void solve() { cin >> n >> MxL; for(int i = 1; i <= n; i++){ cin >> a[i]; } sort(a+1, a+1+n); if(n < 8) Subtask1::process(); else Subtask3::process(); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define name "InvMOD" if(fopen(name".INP", "r")){ freopen(name".INP","r",stdin); freopen(name".OUT","w",stdout); } int t = 1; //cin >> t; while(t--) solve(); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...