QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#53960 | #79. Fabricating Sculptures | not_so_organic | AC ✓ | 105ms | 102292kb | C++20 | 1.5kb | 2022-10-06 13:41:47 | 2022-10-06 13:41:50 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define forn(i,n) for(int i=0; i< (int)n; ++i)
#define for1(i,n) for(int i=1; i<= (int)n; ++i)
#define fore(i,l,r) for(int i=(int)l; i<= (int)r; ++i)
#define ford(i,n) for(int i=(int)(n) - 1; i>= 0; --i)
#define fored(i,l,r) for(int i=(int)r; i>= (int)l; --i)
#define pb push_back
#define el '\n'
#define d(x) cout<< #x<< " " << x<<el
#define ri(n) scanf("%d",&n)
#define sz(v) ((int)v.size())
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> ii;
typedef pair<char,int> pci;
typedef tuple<int, int, int> tiii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
const int inf = 1e9;
const int nax = 5e3+20, mod = 1e9+7;
const ld pi = acos(-1);
const ld eps= 1e-9;
int dp[nax][nax];
inline int add(int a, int b){
if(a+b>=mod) return a+b-mod;
else return a+b;
}
inline int subs(int a, int b){
a-=b;
a%=mod;
if(a<0) return a+mod;
return a;
}
int go(int S, int B){
if(B<0 || S<0){
return 0;
}
if(S==0 && B>=1){
return 0;
}
if(B==0 || S <= 1){
return 1;
}
int &r = dp[S][B];
if(r!=-1) return r;
r = go(S, B-S);
r = add(r, 2*go(S-1, B)%mod);
r = subs(r, go(S-2, B));
return r;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// cout<< setprecision(20)<< fixed;
int S, B;
cin>> S>> B;
memset(dp, -1, sizeof dp);
cout<< go(S, B-S)<<el;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 101968kb
input:
3 6
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 12ms
memory: 101960kb
input:
2 3
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 19ms
memory: 101960kb
input:
3 5
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 28ms
memory: 102072kb
input:
4 6
output:
7
result:
ok single line: '7'
Test #5:
score: 0
Accepted
time: 16ms
memory: 102108kb
input:
5 7
output:
9
result:
ok single line: '9'
Test #6:
score: 0
Accepted
time: 30ms
memory: 102032kb
input:
6 8
output:
11
result:
ok single line: '11'
Test #7:
score: 0
Accepted
time: 23ms
memory: 102020kb
input:
6 9
output:
20
result:
ok single line: '20'
Test #8:
score: 0
Accepted
time: 11ms
memory: 101968kb
input:
4 10
output:
42
result:
ok single line: '42'
Test #9:
score: 0
Accepted
time: 83ms
memory: 102132kb
input:
2505 5000
output:
419207368
result:
ok single line: '419207368'
Test #10:
score: 0
Accepted
time: 94ms
memory: 102184kb
input:
2504 5000
output:
496364578
result:
ok single line: '496364578'
Test #11:
score: 0
Accepted
time: 96ms
memory: 102080kb
input:
2500 5000
output:
806080506
result:
ok single line: '806080506'
Test #12:
score: 0
Accepted
time: 21ms
memory: 102072kb
input:
3 7
output:
12
result:
ok single line: '12'
Test #13:
score: 0
Accepted
time: 95ms
memory: 102184kb
input:
2499 5000
output:
306386138
result:
ok single line: '306386138'
Test #14:
score: 0
Accepted
time: 94ms
memory: 102080kb
input:
2498 5000
output:
788681364
result:
ok single line: '788681364'
Test #15:
score: 0
Accepted
time: 87ms
memory: 102292kb
input:
2497 5000
output:
812170482
result:
ok single line: '812170482'
Test #16:
score: 0
Accepted
time: 105ms
memory: 102204kb
input:
2496 5000
output:
762896457
result:
ok single line: '762896457'
Test #17:
score: 0
Accepted
time: 91ms
memory: 102220kb
input:
2495 5000
output:
110253511
result:
ok single line: '110253511'
Test #18:
score: 0
Accepted
time: 21ms
memory: 102224kb
input:
4123 5000
output:
108131593
result:
ok single line: '108131593'
Test #19:
score: 0
Accepted
time: 33ms
memory: 102200kb
input:
3841 5000
output:
521097090
result:
ok single line: '521097090'
Test #20:
score: 0
Accepted
time: 79ms
memory: 102136kb
input:
1042 5000
output:
193901029
result:
ok single line: '193901029'
Test #21:
score: 0
Accepted
time: 59ms
memory: 102116kb
input:
2109 4000
output:
811834927
result:
ok single line: '811834927'
Test #22:
score: 0
Accepted
time: 50ms
memory: 102168kb
input:
1417 3000
output:
46698841
result:
ok single line: '46698841'
Test #23:
score: 0
Accepted
time: 83ms
memory: 102128kb
input:
2183 5000
output:
373919320
result:
ok single line: '373919320'
Test #24:
score: 0
Accepted
time: 35ms
memory: 102072kb
input:
999 2000
output:
70869124
result:
ok single line: '70869124'
Test #25:
score: 0
Accepted
time: 8ms
memory: 102152kb
input:
566 1000
output:
405298962
result:
ok single line: '405298962'
Test #26:
score: 0
Accepted
time: 12ms
memory: 102040kb
input:
487 1000
output:
456099947
result:
ok single line: '456099947'
Test #27:
score: 0
Accepted
time: 8ms
memory: 101960kb
input:
27 50
output:
569190
result:
ok single line: '569190'
Test #28:
score: 0
Accepted
time: 20ms
memory: 102068kb
input:
33 60
output:
2557608
result:
ok single line: '2557608'
Test #29:
score: 0
Accepted
time: 16ms
memory: 102016kb
input:
66 70
output:
516
result:
ok single line: '516'
Test #30:
score: 0
Accepted
time: 21ms
memory: 102072kb
input:
48 80
output:
17766031
result:
ok single line: '17766031'
Test #31:
score: 0
Accepted
time: 12ms
memory: 101900kb
input:
55 90
output:
47940391
result:
ok single line: '47940391'
Test #32:
score: 0
Accepted
time: 16ms
memory: 102024kb
input:
72 100
output:
9265107
result:
ok single line: '9265107'
Test #33:
score: 0
Accepted
time: 23ms
memory: 101896kb
input:
111 200
output:
991289685
result:
ok single line: '991289685'
Test #34:
score: 0
Accepted
time: 99ms
memory: 102140kb
input:
2503 5000
output:
845880902
result:
ok single line: '845880902'
Test #35:
score: 0
Accepted
time: 20ms
memory: 101964kb
input:
198 300
output:
118013787
result:
ok single line: '118013787'
Test #36:
score: 0
Accepted
time: 15ms
memory: 102008kb
input:
351 400
output:
911070728
result:
ok single line: '911070728'
Test #37:
score: 0
Accepted
time: 22ms
memory: 102028kb
input:
22 500
output:
614964048
result:
ok single line: '614964048'
Test #38:
score: 0
Accepted
time: 16ms
memory: 101984kb
input:
200 500
output:
97398918
result:
ok single line: '97398918'
Test #39:
score: 0
Accepted
time: 17ms
memory: 102052kb
input:
455 500
output:
497174488
result:
ok single line: '497174488'
Test #40:
score: 0
Accepted
time: 20ms
memory: 102024kb
input:
300 600
output:
704360407
result:
ok single line: '704360407'
Test #41:
score: 0
Accepted
time: 4ms
memory: 102156kb
input:
555 700
output:
392947597
result:
ok single line: '392947597'
Test #42:
score: 0
Accepted
time: 8ms
memory: 101992kb
input:
790 800
output:
164231
result:
ok single line: '164231'
Test #43:
score: 0
Accepted
time: 16ms
memory: 102004kb
input:
300 900
output:
281421689
result:
ok single line: '281421689'
Test #44:
score: 0
Accepted
time: 17ms
memory: 102104kb
input:
33 1000
output:
936696284
result:
ok single line: '936696284'
Test #45:
score: 0
Accepted
time: 80ms
memory: 102184kb
input:
2502 5000
output:
595029502
result:
ok single line: '595029502'
Test #46:
score: 0
Accepted
time: 88ms
memory: 102016kb
input:
2501 5000
output:
849299043
result:
ok single line: '849299043'
Test #47:
score: 0
Accepted
time: 8ms
memory: 101900kb
input:
1 1
output:
1
result:
ok single line: '1'
Test #48:
score: 0
Accepted
time: 0ms
memory: 102068kb
input:
1 2
output:
1
result:
ok single line: '1'
Test #49:
score: 0
Accepted
time: 20ms
memory: 101900kb
input:
2 2
output:
1
result:
ok single line: '1'