Submission #1944660


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

const ll MOD = 1000000007;

ll inv[2010];
// n 個の変数 x1, x2, ..., xn に 0 以上の整数を設定して
//  x1 + x2 + ... + xn = v を満たす方法の数。
// n-1 個の | (仕切り)と v 個のボール o の並び替えのパターン数。
// 例えば v=6,n=4 で x={3,2,0,1} は ooo|oo||o と対応する。
// v+n-1 C n-1 が答え。
ll solve(ll n, ll v) {
  ll res = 1;
  for (ll p = v+n-1, q=1; q <= n-1; p--, q++) {
    res *= p;
    res %= MOD;
    res *= inv[q];
    res %= MOD;
  } 
  return res;
}

int A[2000];

int main2() {
  int N = nextInt();
  REP(i, N) A[i] = nextInt();

  ll ans = 1;

  int l = -1;
  REP(i, N) {
    if (A[i] != -1) {
      if (l != -1) {
        ll h = solve(i - l, A[i] - A[l]);
        ans = (ans * h) % MOD;
      }
      l = i;
    }
  }

  cout << ans << endl;
  return 0;
}

int main() {
  inv[1] = 1;
  for (int i = 2; i < 2010; i++) inv[i] = inv[(int) (MOD % i)] * (MOD - MOD / i) % MOD;
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}

Submission Info

Submission Time
Task C - タコヤ木
User hs484
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1582 Byte
Status AC
Exec Time 2 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int nextInt()’:
./Main.cpp:14:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int nextInt() { int x; scanf("%d", &x); return x;}
                                       ^

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 50 / 50 30 / 30 20 / 20
Status
AC × 3
AC × 14
AC × 26
AC × 39
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_12.txt AC 1 ms 256 KB
subtask2_01.txt AC 1 ms 256 KB
subtask2_02.txt AC 1 ms 256 KB
subtask2_03.txt AC 1 ms 256 KB
subtask2_04.txt AC 1 ms 256 KB
subtask2_05.txt AC 2 ms 256 KB
subtask2_06.txt AC 1 ms 256 KB
subtask2_07.txt AC 2 ms 256 KB
subtask2_08.txt AC 2 ms 256 KB
subtask2_09.txt AC 2 ms 256 KB
subtask2_10.txt AC 2 ms 256 KB
subtask2_11.txt AC 2 ms 256 KB
subtask2_12.txt AC 2 ms 256 KB
subtask3_01.txt AC 1 ms 256 KB
subtask3_02.txt AC 1 ms 256 KB
subtask3_03.txt AC 1 ms 256 KB
subtask3_04.txt AC 2 ms 256 KB
subtask3_05.txt AC 1 ms 256 KB
subtask3_06.txt AC 2 ms 256 KB
subtask3_07.txt AC 2 ms 256 KB
subtask3_08.txt AC 2 ms 256 KB
subtask3_09.txt AC 2 ms 256 KB
subtask3_10.txt AC 2 ms 256 KB
subtask3_11.txt AC 2 ms 256 KB
subtask3_12.txt AC 2 ms 256 KB