Submission #3056094
Source Code Expand
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <limits.h>
#include <cstring>
#include <tuple>
#include <cassert>
#include <numeric>
using namespace std;
// type alias
typedef long long LL;
typedef vector < int > VI;
typedef unordered_map < int, int > MAPII;
typedef unordered_set < int > SETI;
typedef pair< int , int > II;
typedef tuple< int, int, int > III;
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n) for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// minmax
#define SMAX(a,b) a = max(a,b)
#define SMIN(a,b) a = min(a,b)
// debug cerr
#define TRACE true
#define dump(x) if(TRACE) { cerr << #x << " = " << (x) << endl; }
#define dump2(x,y) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl; }
#define dump3(x,y,z) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl; }
#define dump4(x,y,z,a) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << ", " << #a << " = " << (a) << endl; }
#define dumpAR(ar) if(TRACE) { FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
/*
8/21/2018
20:35-20:56 analysis
21:27 OMG. maximal total number of kill is 1000 (>100)
*/
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG x.cpp && ./a.out
const int MAX_N=1e2+1;
const int MAX_SUM=1e3+1;
int N,M;
VI A,B;
const LL MOD=1e9+7;
LL memo[MAX_N][MAX_SUM][MAX_SUM];
LL g(int buck, int rem, int last) {
if(buck==0) return rem==0;
if(rem<last) return 0;
LL &res=memo[buck][rem][last];
if(res>=0) return res;
res=0;
FORE(x,last,rem) {
res+=g(buck-1,rem-x,x),res%=MOD;
}
return res;
}
VI G;
LL memo2[MAX_N][MAX_SUM];
LL f(int i, int rem) {
int N=SZ(G);
if(i==N) return rem==0;
LL &res=memo2[i][rem];
if(res>=0) return res;
res=0;
REPE(x,rem) {
//res+=g(G[i],x,0),res%=MOD;
LL y=g(G[i],x,0);
LL z=f(i+1,rem-x);
// dump4(i,G[i],x,y);
y=y*z%MOD;
(res+=y)%=MOD;
}
return res;
}
LL go(VI &X, VI &Y) {
int sum=accumulate(Y.begin(),Y.end(),0);
G.clear();
int cur=X[0],cnt=1;
FOR(i,1,SZ(X)) {
if(X[i]==X[i-1]) ++cnt;
else {
G.push_back(cnt);
cnt=1,cur=X[i];
}
}
if(cnt>0) G.push_back(cnt);
// dump(sum);
// dumpAR(G);
MINUS(memo2);
return f(0,sum);
}
LL solve() {
MINUS(memo);
LL x=go(A,B),y=go(B,A);
// LL x=1,y=1;
// dump(g(4,5,0));
// dump2(x,y);
return x*y%MOD;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N>>M;
A.resize(N),B.resize(M);
REP(i,N) cin>>A[i];
REP(i,M) cin>>B[i];
cout<<solve()<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Kill/Death |
User |
kumalimak |
Language |
C++14 (Clang 3.8.0) |
Score |
0 |
Code Size |
3278 Byte |
Status |
TLE |
Exec Time |
2658 ms |
Memory |
791680 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 500 |
Status |
|
Set Name |
Test Cases |
All |
01_sample00, 01_sample01, 01_sample02, 01_sample03, 01_sample04, 02_minimal00, 02_minimal01, 02_minimal02, 02_minimal03, 03_maximal00, 03_maximal01, 04_random-easy00, 04_random-easy01, 04_random-easy02, 04_random-easy03, 04_random-easy04, 04_random-easy05, 04_random-easy06, 04_random-easy07, 04_random-easy08, 04_random-easy09, 04_random-easy10, 04_random-easy11, 04_random-easy12, 04_random-easy13, 04_random-easy14, 04_random-easy15, 04_random-easy16, 04_random-easy17, 04_random-easy18, 04_random-easy19, 05_random-large00, 05_random-large01, 05_random-large02, 05_random-large03, 05_random-large04, 05_random-large05, 05_random-large06, 05_random-large07, 05_random-large08, 05_random-large09, 05_random-large10, 05_random-large11, 05_random-large12, 05_random-large13, 05_random-large14, 05_random-large15, 05_random-large16, 05_random-large17, 05_random-large18, 05_random-large19, 06_random00, 06_random01, 06_random02, 06_random03, 06_random04, 06_random05, 06_random06, 06_random07, 06_random08, 06_random09, 06_random10, 06_random11, 06_random12, 06_random13, 06_random14, 06_random15, 06_random16, 06_random17, 06_random18, 06_random19 |
Case Name |
Status |
Exec Time |
Memory |
01_sample00 |
MLE |
192 ms |
791680 KB |
01_sample01 |
MLE |
192 ms |
791680 KB |
01_sample02 |
MLE |
192 ms |
791680 KB |
01_sample03 |
MLE |
192 ms |
791680 KB |
01_sample04 |
MLE |
444 ms |
791680 KB |
02_minimal00 |
MLE |
191 ms |
791680 KB |
02_minimal01 |
MLE |
195 ms |
791680 KB |
02_minimal02 |
MLE |
195 ms |
791680 KB |
02_minimal03 |
MLE |
195 ms |
791680 KB |
03_maximal00 |
TLE |
2658 ms |
791680 KB |
03_maximal01 |
TLE |
2657 ms |
791680 KB |
04_random-easy00 |
MLE |
191 ms |
791680 KB |
04_random-easy01 |
MLE |
192 ms |
791680 KB |
04_random-easy02 |
MLE |
192 ms |
791680 KB |
04_random-easy03 |
MLE |
191 ms |
791680 KB |
04_random-easy04 |
MLE |
192 ms |
791680 KB |
04_random-easy05 |
MLE |
191 ms |
791680 KB |
04_random-easy06 |
MLE |
192 ms |
791680 KB |
04_random-easy07 |
MLE |
192 ms |
791680 KB |
04_random-easy08 |
MLE |
192 ms |
791680 KB |
04_random-easy09 |
MLE |
192 ms |
791680 KB |
04_random-easy10 |
MLE |
192 ms |
791680 KB |
04_random-easy11 |
MLE |
191 ms |
791680 KB |
04_random-easy12 |
MLE |
191 ms |
791680 KB |
04_random-easy13 |
MLE |
191 ms |
791680 KB |
04_random-easy14 |
MLE |
191 ms |
791680 KB |
04_random-easy15 |
MLE |
191 ms |
791680 KB |
04_random-easy16 |
MLE |
191 ms |
791680 KB |
04_random-easy17 |
MLE |
191 ms |
791680 KB |
04_random-easy18 |
MLE |
191 ms |
791680 KB |
04_random-easy19 |
MLE |
191 ms |
791680 KB |
05_random-large00 |
TLE |
2658 ms |
791680 KB |
05_random-large01 |
TLE |
2657 ms |
791680 KB |
05_random-large02 |
TLE |
2658 ms |
791680 KB |
05_random-large03 |
TLE |
2658 ms |
791680 KB |
05_random-large04 |
TLE |
2657 ms |
791680 KB |
05_random-large05 |
TLE |
2657 ms |
791680 KB |
05_random-large06 |
TLE |
2658 ms |
791680 KB |
05_random-large07 |
TLE |
2658 ms |
791680 KB |
05_random-large08 |
TLE |
2657 ms |
791680 KB |
05_random-large09 |
TLE |
2658 ms |
791680 KB |
05_random-large10 |
TLE |
2658 ms |
791680 KB |
05_random-large11 |
TLE |
2657 ms |
791680 KB |
05_random-large12 |
TLE |
2657 ms |
791680 KB |
05_random-large13 |
TLE |
2658 ms |
791680 KB |
05_random-large14 |
TLE |
2658 ms |
791680 KB |
05_random-large15 |
TLE |
2657 ms |
791680 KB |
05_random-large16 |
TLE |
2658 ms |
791680 KB |
05_random-large17 |
TLE |
2657 ms |
791680 KB |
05_random-large18 |
TLE |
2658 ms |
791680 KB |
05_random-large19 |
TLE |
2657 ms |
791680 KB |
06_random00 |
TLE |
2658 ms |
791680 KB |
06_random01 |
MLE |
283 ms |
791680 KB |
06_random02 |
TLE |
2657 ms |
791680 KB |
06_random03 |
MLE |
1278 ms |
791680 KB |
06_random04 |
TLE |
2658 ms |
791680 KB |
06_random05 |
MLE |
1258 ms |
791680 KB |
06_random06 |
MLE |
315 ms |
791680 KB |
06_random07 |
TLE |
2658 ms |
791680 KB |
06_random08 |
MLE |
548 ms |
791680 KB |
06_random09 |
MLE |
1329 ms |
791680 KB |
06_random10 |
TLE |
2657 ms |
791680 KB |
06_random11 |
TLE |
2658 ms |
791680 KB |
06_random12 |
MLE |
1406 ms |
791680 KB |
06_random13 |
MLE |
314 ms |
791680 KB |
06_random14 |
MLE |
1523 ms |
791680 KB |
06_random15 |
MLE |
197 ms |
791680 KB |
06_random16 |
TLE |
2657 ms |
791680 KB |
06_random17 |
MLE |
1210 ms |
791680 KB |
06_random18 |
TLE |
2657 ms |
791680 KB |
06_random19 |
MLE |
554 ms |
791680 KB |