QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#223276 | #3592. Leaving Yharnam | atoiz | AC ✓ | 24ms | 26960kb | C++14 | 2.0kb | 2023-10-21 23:25:13 | 2023-10-21 23:25:13 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 2000007;
int add(int a, int b) { a += b; return a -= (a >= MOD ? MOD : 0); }
int sub(int a, int b) { a -= b; return a += (a < 0 ? MOD : 0); }
int mul(int a, int b) { return (int) ((int64_t) a * b % MOD); }
int bpow(int a, int p) {
int x = 1;
for (; p; p >>= 1) {
if (p & 1) x = mul(x, a);
a = mul(a, a);
}
return x;
}
int fact[MAXN], ifact[MAXN], pow2[MAXN], N, G, I, E;
int choose(int n, int k) {
return mul(fact[n], mul(fact[k], fact[n-k]));
}
int main() {
cin >> N >> G >> I >> E;
fact[0] = 1;
for (int i = 1; i <= 2*N; ++i) fact[i] = mul(fact[i-1], i);
ifact[2*N] = bpow(fact[2*N], MOD - 2);
for (int i = N*2-1; i >= 0; --i) ifact[i] = mul(ifact[i+1], i+1);
pow2[0] = 1;
for (int i = 1; i <= 2*N; ++i) pow2[i] = add(pow2[i-1], pow2[i-1]);
G = min(G, N*2);
E = min(E, N*2-G);
I = min(I, N*2-G-E);
int ans = 0;
for (int a = 0; a <= N; ++a) {
int b = G - a * 2, c = N - a - b;
if (b < 0 || c < 0) continue;
int probAB = 1, score = G;
probAB = mul(probAB, fact[N]);
probAB = mul(probAB, ifact[a]);
probAB = mul(probAB, ifact[b]);
probAB = mul(probAB, ifact[N-a-b]);
probAB = mul(probAB, pow2[b]);
probAB = mul(probAB, ifact[2*N]);
probAB = mul(probAB, fact[2*N-G]);
probAB = mul(probAB, fact[G]);
bool remainingE = 0;
if (b < E) {
remainingE = (E-b) & 1;
score += E - remainingE;
c -= (E-b) / 2 + remainingE;
b = remainingE;
} else {
b -= E;
score += E;
}
// cout << a << ' ' << b << ' ' << c << " - " << I << endl;
if (c >= I) {
score += I;
} else {
score += c;
int rI = I - c;
if (remainingE) {
remainingE = 0;
score += 1;
--b;
--rI;
}
if (rI > b) score -= rI - b;
}
// cout << a << ": " << probAB << ' ' << score << endl;
ans = add(ans, mul(probAB, score));
}
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7816kb
input:
1 0 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
10 5 13 11
output:
16
result:
ok single line: '16'
Test #3:
score: 0
Accepted
time: 8ms
memory: 14684kb
input:
324005 203143 770973 565020
output:
648010
result:
ok single line: '648010'
Test #4:
score: 0
Accepted
time: 24ms
memory: 25428kb
input:
783794 966573 337313 49232
output:
658568709
result:
ok single line: '658568709'
Test #5:
score: 0
Accepted
time: 8ms
memory: 14832kb
input:
224046 630433 450997 667681
output:
448092
result:
ok single line: '448092'
Test #6:
score: 0
Accepted
time: 1ms
memory: 7800kb
input:
5 20 2 13
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7820kb
input:
4 0 10 14
output:
8
result:
ok single line: '8'
Test #8:
score: 0
Accepted
time: 1ms
memory: 7676kb
input:
1 19 17 3
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 1ms
memory: 7744kb
input:
2 20 19 1
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
18 11 4 15
output:
30
result:
ok single line: '30'
Test #11:
score: 0
Accepted
time: 1ms
memory: 7804kb
input:
6 1 13 18
output:
12
result:
ok single line: '12'
Test #12:
score: 0
Accepted
time: 1ms
memory: 7760kb
input:
19 12 2 19
output:
32
result:
ok single line: '32'
Test #13:
score: 0
Accepted
time: 1ms
memory: 7764kb
input:
1 2 5 8
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 1ms
memory: 7680kb
input:
20 5 2 18
output:
24
result:
ok single line: '24'
Test #15:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
10 0 11 0
output:
9
result:
ok single line: '9'
Test #16:
score: 0
Accepted
time: 0ms
memory: 7748kb
input:
10 3 9 6
output:
11
result:
ok single line: '11'
Test #17:
score: 0
Accepted
time: 1ms
memory: 7808kb
input:
16 13 13 14
output:
27
result:
ok single line: '27'
Test #18:
score: 0
Accepted
time: 1ms
memory: 7808kb
input:
20 16 12 0
output:
153846178
result:
ok single line: '153846178'
Test #19:
score: 0
Accepted
time: 0ms
memory: 7812kb
input:
20 3 4 3
output:
10
result:
ok single line: '10'
Test #20:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
8 16 19 14
output:
16
result:
ok single line: '16'
Test #21:
score: 0
Accepted
time: 0ms
memory: 7608kb
input:
17 4 5 11
output:
19
result:
ok single line: '19'
Test #22:
score: 0
Accepted
time: 1ms
memory: 7736kb
input:
8 12 8 13
output:
16
result:
ok single line: '16'
Test #23:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
19 18 4 18
output:
36
result:
ok single line: '36'
Test #24:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
5 14 8 0
output:
10
result:
ok single line: '10'
Test #25:
score: 0
Accepted
time: 0ms
memory: 7812kb
input:
2 5 1 17
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 0ms
memory: 7628kb
input:
2 2 1 0
output:
333333338
result:
ok single line: '333333338'
Test #27:
score: 0
Accepted
time: 1ms
memory: 7632kb
input:
10 1 0 2
output:
2
result:
ok single line: '2'
Test #28:
score: 0
Accepted
time: 1ms
memory: 7812kb
input:
10 17 10 0
output:
17
result:
ok single line: '17'
Test #29:
score: 0
Accepted
time: 1ms
memory: 7680kb
input:
15 2 8 6
output:
16
result:
ok single line: '16'
Test #30:
score: 0
Accepted
time: 1ms
memory: 7816kb
input:
3 4 2 1
output:
5
result:
ok single line: '5'
Test #31:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
10 18 3 18
output:
20
result:
ok single line: '20'
Test #32:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
20 18 19 5
output:
23
result:
ok single line: '23'
Test #33:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
9 2 7 7
output:
11
result:
ok single line: '11'
Test #34:
score: 0
Accepted
time: 1ms
memory: 7764kb
input:
11 12 3 9
output:
21
result:
ok single line: '21'
Test #35:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
10 8 2 8
output:
18
result:
ok single line: '18'
Test #36:
score: 0
Accepted
time: 1ms
memory: 7680kb
input:
17 11 2 9
output:
22
result:
ok single line: '22'
Test #37:
score: 0
Accepted
time: 0ms
memory: 7820kb
input:
11 10 15 6
output:
16
result:
ok single line: '16'
Test #38:
score: 0
Accepted
time: 1ms
memory: 7768kb
input:
1 14 16 5
output:
2
result:
ok single line: '2'
Test #39:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
9 8 10 3
output:
11
result:
ok single line: '11'
Test #40:
score: 0
Accepted
time: 0ms
memory: 7832kb
input:
9 8 8 3
output:
11
result:
ok single line: '11'
Test #41:
score: 0
Accepted
time: 1ms
memory: 7808kb
input:
9 1 3 10
output:
13
result:
ok single line: '13'
Test #42:
score: 0
Accepted
time: 0ms
memory: 7688kb
input:
1000 500 0 0
output:
500
result:
ok single line: '500'
Test #43:
score: 0
Accepted
time: 0ms
memory: 7776kb
input:
1000 1000 0 0
output:
1000
result:
ok single line: '1000'
Test #44:
score: 0
Accepted
time: 0ms
memory: 7756kb
input:
1000 1500 0 0
output:
1500
result:
ok single line: '1500'
Test #45:
score: 0
Accepted
time: 1ms
memory: 7812kb
input:
1000 2000 0 0
output:
2000
result:
ok single line: '2000'
Test #46:
score: 0
Accepted
time: 1ms
memory: 7636kb
input:
1000 2500 0 0
output:
2000
result:
ok single line: '2000'
Test #47:
score: 0
Accepted
time: 1ms
memory: 7720kb
input:
1000 0 500 0
output:
500
result:
ok single line: '500'
Test #48:
score: 0
Accepted
time: 1ms
memory: 7812kb
input:
10 1 18 2
output:
3
result:
ok single line: '3'
Test #49:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
1000 0 1000 0
output:
1000
result:
ok single line: '1000'
Test #50:
score: 0
Accepted
time: 1ms
memory: 7776kb
input:
1000 0 1500 0
output:
500
result:
ok single line: '500'
Test #51:
score: 0
Accepted
time: 1ms
memory: 7836kb
input:
1000 0 2000 0
output:
0
result:
ok single line: '0'
Test #52:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
1000 0 2500 0
output:
0
result:
ok single line: '0'
Test #53:
score: 0
Accepted
time: 1ms
memory: 7828kb
input:
1000 0 0 500
output:
500
result:
ok single line: '500'
Test #54:
score: 0
Accepted
time: 1ms
memory: 7812kb
input:
1000 0 0 1000
output:
1000
result:
ok single line: '1000'
Test #55:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
1000 0 0 1500
output:
1500
result:
ok single line: '1500'
Test #56:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
1000 0 0 2000
output:
2000
result:
ok single line: '2000'
Test #57:
score: 0
Accepted
time: 1ms
memory: 7836kb
input:
1000 0 0 2500
output:
2000
result:
ok single line: '2000'
Test #58:
score: 0
Accepted
time: 1ms
memory: 7776kb
input:
1000 300 300 0
output:
600
result:
ok single line: '600'
Test #59:
score: 0
Accepted
time: 1ms
memory: 7812kb
input:
1 11 0 11
output:
2
result:
ok single line: '2'
Test #60:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
1000 500 500 0
output:
1000
result:
ok single line: '1000'
Test #61:
score: 0
Accepted
time: 1ms
memory: 7776kb
input:
1000 700 700 0
output:
158494380
result:
ok single line: '158494380'
Test #62:
score: 0
Accepted
time: 1ms
memory: 7692kb
input:
1000 1000 1000 0
output:
1000
result:
ok single line: '1000'
Test #63:
score: 0
Accepted
time: 1ms
memory: 7684kb
input:
1000 1500 1500 0
output:
1500
result:
ok single line: '1500'
Test #64:
score: 0
Accepted
time: 1ms
memory: 7820kb
input:
1000 2000 2000 0
output:
2000
result:
ok single line: '2000'
Test #65:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
1000 300 0 300
output:
600
result:
ok single line: '600'
Test #66:
score: 0
Accepted
time: 1ms
memory: 7820kb
input:
1000 500 0 500
output:
1000
result:
ok single line: '1000'
Test #67:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
1000 700 0 700
output:
1400
result:
ok single line: '1400'
Test #68:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
1000 1000 0 1000
output:
2000
result:
ok single line: '2000'
Test #69:
score: 0
Accepted
time: 1ms
memory: 7760kb
input:
1000 1500 0 1500
output:
2000
result:
ok single line: '2000'
Test #70:
score: 0
Accepted
time: 1ms
memory: 7744kb
input:
19 12 14 10
output:
24
result:
ok single line: '24'
Test #71:
score: 0
Accepted
time: 1ms
memory: 7636kb
input:
1000 2000 0 2000
output:
2000
result:
ok single line: '2000'
Test #72:
score: 0
Accepted
time: 0ms
memory: 7764kb
input:
1000 0 300 300
output:
600
result:
ok single line: '600'
Test #73:
score: 0
Accepted
time: 0ms
memory: 7772kb
input:
1000 0 500 500
output:
1000
result:
ok single line: '1000'
Test #74:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
1000 0 700 700
output:
1300
result:
ok single line: '1300'
Test #75:
score: 0
Accepted
time: 0ms
memory: 7768kb
input:
1000 0 1000 1000
output:
1000
result:
ok single line: '1000'
Test #76:
score: 0
Accepted
time: 1ms
memory: 7836kb
input:
1000 0 1500 1500
output:
1500
result:
ok single line: '1500'
Test #77:
score: 0
Accepted
time: 1ms
memory: 7816kb
input:
1000 0 2000 2000
output:
2000
result:
ok single line: '2000'
Test #78:
score: 0
Accepted
time: 1ms
memory: 7704kb
input:
2637 6773 9174 1735
output:
5274
result:
ok single line: '5274'
Test #79:
score: 0
Accepted
time: 1ms
memory: 7784kb
input:
2703 8304 3387 1641
output:
5406
result:
ok single line: '5406'
Test #80:
score: 0
Accepted
time: 1ms
memory: 7792kb
input:
6326 8700 3534 6848
output:
12652
result:
ok single line: '12652'
Test #81:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
15 15 12 17
output:
30
result:
ok single line: '30'
Test #82:
score: 0
Accepted
time: 1ms
memory: 7764kb
input:
2142 6609 4924 4096
output:
4284
result:
ok single line: '4284'
Test #83:
score: 0
Accepted
time: 1ms
memory: 7744kb
input:
9565 8872 6950 5722
output:
14594
result:
ok single line: '14594'
Test #84:
score: 0
Accepted
time: 1ms
memory: 7744kb
input:
547 2715 9932 9784
output:
1094
result:
ok single line: '1094'
Test #85:
score: 0
Accepted
time: 0ms
memory: 7628kb
input:
88 2600 8625 3878
output:
176
result:
ok single line: '176'
Test #86:
score: 0
Accepted
time: 1ms
memory: 7772kb
input:
1661 8169 2242 4146
output:
3322
result:
ok single line: '3322'
Test #87:
score: 0
Accepted
time: 1ms
memory: 7712kb
input:
4167 1089 8718 9606
output:
8334
result:
ok single line: '8334'
Test #88:
score: 0
Accepted
time: 1ms
memory: 7776kb
input:
4463 553 8538 5105
output:
5658
result:
ok single line: '5658'
Test #89:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
8142 9612 4922 8312
output:
16284
result:
ok single line: '16284'
Test #90:
score: 0
Accepted
time: 1ms
memory: 7804kb
input:
6612 6829 2173 4699
output:
11528
result:
ok single line: '11528'
Test #91:
score: 0
Accepted
time: 1ms
memory: 7832kb
input:
3435 7847 5234 2646
output:
6870
result:
ok single line: '6870'
Test #92:
score: 0
Accepted
time: 0ms
memory: 7748kb
input:
17 13 18 18
output:
31
result:
ok single line: '31'
Test #93:
score: 0
Accepted
time: 0ms
memory: 7768kb
input:
3425 9920 1367 7901
output:
6850
result:
ok single line: '6850'
Test #94:
score: 0
Accepted
time: 1ms
memory: 7904kb
input:
9741 9676 483 2051
output:
330597298
result:
ok single line: '330597298'
Test #95:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
2324 2737 5161 8088
output:
4648
result:
ok single line: '4648'
Test #96:
score: 0
Accepted
time: 0ms
memory: 7808kb
input:
6606 1493 824 9179
output:
11496
result:
ok single line: '11496'
Test #97:
score: 0
Accepted
time: 1ms
memory: 7812kb
input:
8265 9267 238 7595
output:
16530
result:
ok single line: '16530'
Test #98:
score: 0
Accepted
time: 0ms
memory: 7860kb
input:
6992 6132 164 5228
output:
11524
result:
ok single line: '11524'
Test #99:
score: 0
Accepted
time: 1ms
memory: 7712kb
input:
3647 6343 9074 4888
output:
7294
result:
ok single line: '7294'
Test #100:
score: 0
Accepted
time: 24ms
memory: 26960kb
input:
761933 965642 909762 628739
output:
1523866
result:
ok single line: '1523866'
Test #101:
score: 0
Accepted
time: 16ms
memory: 22944kb
input:
661992 436246 405301 690525
output:
1126771
result:
ok single line: '1126771'
Test #102:
score: 0
Accepted
time: 22ms
memory: 26072kb
input:
799120 245571 55209 777457
output:
1078237
result:
ok single line: '1078237'