제출 #1010561

#제출 시각아이디문제언어결과실행 시간메모리
1010561Beerus13Trains (BOI24_trains)C++17
37 / 100
174 ms129932 KiB
#include<bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; --i) #define REP(i, a, b) for(int i = (a), _b = (b); i < _b; ++i) #define REPD(i, b, a) for(int i = (b), _a = (a); i > _a; --i) #define MASK(i) (1LL << (i)) #define BIT(mask, i) (((mask) >> (i)) & 1) #define __builtin_popcount __builtin_popcountll #define all(val) val.begin(), val.end() #define ll long long #define ull unsigned long long #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll Rand(ll l, ll r) {return l + rng() % (r - l + 1);} template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } else return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } else return false; } template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); } const int N = 1e5 + 5; const int sqr = 320; const int mod = 1e9 + 7; void add(int &a, const int &b) { a += b; if(a >= mod) a -= mod; if(a < 0) a += mod; } int mul(const int &a, const int &b) { return 1ll * a * b % mod; } int n, d[N], x[N]; int dp[N], f[N][sqr + 5]; int check1, check2; void sub2() { if(n > 1e4) return; dp[1] = 1; int res = 0; FOR(i, 1, n) if(x[i] && d[i]) { FOR(j, 1, x[i]) { if(i + j * d[i] > n) break; add(dp[i + j * d[i]], dp[i]); } } FOR(i, 1, n) add(res, dp[i]); check1 = res; cout << res << '\n'; exit(0); } void sub5() { dp[1] = 1; int res = 0; FOR(i, 1, n) { FOR(k, 1, sqr) { if(i >= k) add(f[i][k], f[i - k][k]); add(dp[i], f[i][k]); } if(d[i] == 0 || x[i] == 0) continue; if(d[i] > sqr) { FOR(j, 1, x[i]) { if(i + j * d[i] > n) break; add(dp[i + j * d[i]], dp[i]); } } else { add(f[i][d[i]], dp[i]); int mx = 1ll * d[i] * (x[i] + 1); if(i + mx <= n) add(f[i + mx][d[i]], -dp[i]); } } FOR(i, 1, n) add(res, dp[i]); check2 = res; cout << res << '\n'; exit(0); } void sinhtest() { int ntests = 10; while(ntests--) { n = Rand(1, 1e3); FOR(i, 1, n) { d[i] = Rand(0, 1e9); x[i] = Rand(0, 1e9); } memset(dp, 0, sizeof(dp)); FOR(i, 1, n) memset(f[i], 0, sizeof(f[i])); sub2(); memset(dp, 0, sizeof(dp)); sub5(); if(check1 == check2) cout << "CORRECT\n"; else { cout << "INCORRECT\n"; cout << n << '\n'; FOR(i, 1, n) cout << d[i] << ' ' << x[i] << '\n'; return; } } } void process() { cin >> n; FOR(i, 1, n) cin >> d[i] >> x[i]; sub2(); sub5(); } signed main() { if(fopen("test.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ntests = 1; // cin >> ntests; while(ntests--) process(); return 0; }

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

Main.cpp: In function 'int main()':
Main.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...