Submission #1188207
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-10;
int n, c;
int a[400], b[400];
ll dp[401][401];
ll pw[400][401], tmp[401];
ll dfs(int pos, int cnt) {
if (pos == n) return cnt == c;
if (~dp[pos][cnt]) return dp[pos][cnt];
ll res = 0, p = 1;
REP(i, c - cnt + 1)
(res += dfs(pos + 1, cnt + i) * pw[pos][i] % MOD) %= MOD;
return dp[pos][cnt] = res;
}
int main() {
cin >> n >> c;
REP(i, n) scanf("%d", a + i);
REP(i, n) scanf("%d", b + i);
REP(i, n) {
REP(j, a[i]) tmp[j] = 0;
FOR(j, a[i], b[i] + 1) tmp[j] = 1;
REP(j, c + 1) {
ll now = 0;
FOR(k, a[i], b[i] + 1) (now += tmp[k]) %= MOD;
pw[i][j] = now;
FOR(k, a[i], b[i] + 1) tmp[k] = tmp[k] * k % MOD;
}
}
fill(dp[0], dp[n + 1], -1);
cout << dfs(0, 0) << endl;
return 0;
}
Submission Info
Submission Time
2017-03-28 17:48:46+0900
Task
E - Children and Candies
User
tkmst201
Language
C++14 (GCC 5.4.1)
Score
800
Code Size
1336 Byte
Status
AC
Exec Time
618 ms
Memory
2816 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:40:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i, n) scanf("%d", a + i);
^
./Main.cpp:41:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i, n) scanf("%d", b + i);
^
Judge Result
Set Name
Sample
Subtask
All
Score / Max Score
0 / 0
400 / 400
400 / 400
Status
Set Name
Test Cases
Sample
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt
Subtask
0_001, 0_003, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt
All
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 2_017.txt, 2_018.txt, 2_019.txt, 2_020.txt, 2_021.txt, 2_022.txt, 2_023.txt, 2_024.txt, 2_025.txt, 2_026.txt, 2_027.txt, 2_028.txt, 2_029.txt
Case Name
Status
Exec Time
Memory
0_000.txt
AC
1 ms
256 KB
0_001.txt
AC
1 ms
256 KB
0_002.txt
AC
1 ms
256 KB
0_003.txt
AC
1 ms
256 KB
0_004.txt
AC
1 ms
256 KB
1_005.txt
AC
1 ms
256 KB
1_006.txt
AC
1 ms
256 KB
1_007.txt
AC
1 ms
256 KB
1_008.txt
AC
1 ms
256 KB
1_009.txt
AC
1 ms
256 KB
1_010.txt
AC
1 ms
256 KB
1_011.txt
AC
2 ms
2816 KB
1_012.txt
AC
2 ms
2816 KB
1_013.txt
AC
2 ms
2816 KB
1_014.txt
AC
233 ms
2816 KB
1_015.txt
AC
233 ms
2816 KB
1_016.txt
AC
233 ms
2816 KB
2_017.txt
AC
1 ms
256 KB
2_018.txt
AC
1 ms
256 KB
2_019.txt
AC
2 ms
256 KB
2_020.txt
AC
2 ms
256 KB
2_021.txt
AC
4 ms
2816 KB
2_022.txt
AC
3 ms
2816 KB
2_023.txt
AC
618 ms
2816 KB
2_024.txt
AC
365 ms
2816 KB
2_025.txt
AC
87 ms
2816 KB
2_026.txt
AC
8 ms
2304 KB
2_027.txt
AC
294 ms
2560 KB
2_028.txt
AC
12 ms
1024 KB
2_029.txt
AC
4 ms
512 KB