Submission #1116108

#TimeUsernameProblemLanguageResultExecution timeMemory
1116108vjudge1Calvinball championship (CEOI15_teams)C++17
10 / 100
87 ms42568 KiB
#include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "/home/ahmetalp/Desktop/Workplace/debug.h" #else #define debug(...) void(23) #endif template<typename T> T power(T a, i64 b) { T res = 1; while(b) { if(b & 1) { res *= a; } a *= a; b >>= 1; } return res; } constexpr int md = int(1E6) + 7; struct MInt { int val; MInt() : val(0) {} template<typename T> MInt(T v) { if(-md <= v && v < md) { val = v; } else { val = v % md; } if(val < 0) { val += md; } } int operator() () { return val; } MInt operator+= (MInt rhs) { if((val += rhs.val) >= md) { val -= md; } return *this; } MInt operator-= (MInt rhs) { if((val -= rhs.val) < 0) { val += md; } return *this; } MInt operator*= (MInt rhs) { val = (int)(1LL * val * rhs.val % md); return *this; } MInt inv() { return power(*this, md - 2); } MInt operator/= (MInt rhs) { return *this *= rhs.inv(); } bool operator== (MInt rhs) { return val == rhs.val; } bool operator!= (MInt rhs) { return val != rhs.val; } }; MInt operator+ (MInt lhs, MInt rhs) { return lhs += rhs; } MInt operator- (MInt lhs, MInt rhs) { return lhs -= rhs; } MInt operator* (MInt lhs, MInt rhs) { return lhs *= rhs; } MInt operator/ (MInt lhs, MInt rhs) { return lhs /= rhs; } std::ostream& operator<< (std::ostream& os, MInt v) { return os << v(); } std::string to_string(MInt x) { return to_string(x()); } using Z = MInt; constexpr int max_N = 200 + 5; int N; int A[max_N]; int mxc[max_N], usedc[max_N]; std::map<int, int> visc; bool vis[max_N][max_N][max_N]; Z dp[max_N][max_N][max_N]; Z f(int x, int y, int z) { if (x == 0) { debug(x, y, z, y == z); return y == z; } else if (vis[x][y][z]) { debug(x, y, z, dp[x][y][z]); return dp[x][y][z]; } vis[x][y][z] = true; Z& ans = dp[x][y][z]; ans += f(x - 1, y, z) * z; ans += f(x - 1, y, z + 1) * (y - z); debug(x, y, z, ans); return ans; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> N; for (int i = 1; i <= N; ++i) { std::cin >> A[i]; } Z ans = 0; for (int i = 1; i <= N; ++i) { for (int j = 1; j < A[i]; ++j) { int gap = N - i; int had = usedc[i - 1] + !visc[j]; for (int k = std::max(mxc[i - 1], j); k <= N; ++k) { int need = k - had; if (need <= gap) { Z x = f(gap, k, had); debug(i, j, k, gap, had, need, x); ans += x; } } } mxc[i] = std::max(mxc[i - 1], A[i]); usedc[i] = usedc[i - 1] + !visc[A[i]]; visc[A[i]] = true; } bool good = true; for (int i = 1; i <= mxc[i]; ++i) { good &= visc[i]; } ans += good; std::cout << ans << '\n'; return 0; }

Compilation message (stderr)

teams.cpp: In instantiation of 'MInt::MInt(T) [with T = bool]':
teams.cpp:102:21:   required from here
teams.cpp:30:16: warning: comparison of constant '-1000007' with boolean expression is always true [-Wbool-compare]
   30 |         if(-md <= v && v < md) {
      |            ~~~~^~~~
teams.cpp:30:26: warning: comparison of constant '1000007' with boolean expression is always true [-Wbool-compare]
   30 |         if(-md <= v && v < md) {
      |                        ~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...