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
TLE × 30
MLE × 41
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