제출 #781200

#제출 시각아이디문제언어결과실행 시간메모리
781200skittles1412Linear Garden (IOI08_linear_garden)C++17
90 / 100
137 ms65536 KiB
#include "bits/extc++.h" using namespace std; template <typename T, typename... U> void dbgh(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; } #ifdef DEBUG #define dbg(...) \ cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \ << ": "; \ dbgh(__VA_ARGS__) #else #define cerr \ if (false) \ cerr #define dbg(...) #endif #define endl "\n" #define long int64_t #define sz(x) int(std::size(x)) int MOD; struct mint { static int norm(long x) { x %= MOD; if (x < 0) { x += MOD; } return int(x); } int x; mint() : x(0) {} mint(long x) : x(norm(x)) {} static mint from_unchecked(int x) { mint m; m.x = x; return m; } friend ostream& operator<<(ostream& out, const mint& m) { return out << m.x; } mint operator-() const { if (!x) { return {}; } else { return mint::from_unchecked(MOD - x); } } mint& operator+=(const mint& m) { x += m.x; if (x >= MOD) { x -= MOD; } return *this; } mint& operator-=(const mint& m) { return *this += -m; } mint& operator*=(const mint& m) { x = int(long(x) * m.x % MOD); return *this; } friend mint operator+(mint a, const mint& b) { return a += b; } friend mint operator-(mint a, const mint& b) { return a -= b; } friend mint operator*(mint a, const mint& b) { return a *= b; } }; struct Solver { int n, ql, qr; const vector<int>& arr; vector<array<mint, 6>> memo; Solver(const vector<int>& arr, int ql, int qr) : n(sz(arr)), arr(arr), ql(ql), qr(qr), memo(n) { for (auto& a : memo) { a.fill(mint::from_unchecked(-1)); } } mint dp(int ind, int psum, bool lt) { if (!(ql <= psum && psum <= qr)) { return 0; } else if (ind == n) { return lt; } mint& ans = memo[ind][(psum - ql) * 2 + lt]; if (ans.x != -1) { return ans; } ans = 0; for (int x : {-1, +1}) { if (!lt && x > arr[ind]) { continue; } ans += dp(ind + 1, psum + x, lt || (x < arr[ind])); } return ans; } mint solve() { return dp(0, 0, false); } }; void solve() { int n; cin >> n >> MOD; vector<int> arr(n); { string s; cin >> s; for (int i = 0; i < n; i++) { if (s[i] == 'L') { arr[i] = -1; } else { assert(s[i] == 'P'); arr[i] = +1; } } } auto solve = [&](int ql, int qr) -> mint { return Solver(arr, ql, qr).solve(); }; cout << solve(-2, 0) + solve(-1, 1) + solve(0, 2) - solve(-1, 0) - solve(0, 1) + 1 << endl; } int main() { cin.tie(nullptr); cin.exceptions(ios::failbit); ios_base::sync_with_stdio(false); solve(); }

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

linear_garden.cpp: In constructor 'Solver::Solver(const std::vector<int>&, int, int)':
linear_garden.cpp:91:24: warning: 'Solver::arr' will be initialized after [-Wreorder]
   91 |     const vector<int>& arr;
      |                        ^~~
linear_garden.cpp:90:12: warning:   'int Solver::ql' [-Wreorder]
   90 |     int n, ql, qr;
      |            ^~
linear_garden.cpp:94:5: warning:   when initialized here [-Wreorder]
   94 |     Solver(const vector<int>& arr, int ql, int qr)
      |     ^~~~~~
#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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...