oj.uz

Submission #6324

# Submission time Handle Problem Language Result Execution time Memory
6324 2014-06-28T07:07:26 Z jhs7jhs 없는 등수 찾기 (GA7_rank) C++
30 / 100
 0 ms 2496 KB 
#include<stdio.h>

int n,m;
long long man[300][2]={{0}};
long long dp[300][300]={{0}},dp2[300][300]={{0}};
int main()
{
    long long MD = 10000000007;
    long long p,q,r,ans=0,all=1;
    int i,j,k,ra;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&man[i][0],&man[i][1]);
        all *= (man[i][1] - man[i][0] + 1);
        all %= MD;
    }
    scanf("%d",&ra);
    if(ra == 1){
        printf("0\n");
        return 0;
    }
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            for(k=0;k<ra;k++) dp[j][k] = dp2[j][k] = 0;
        }
        p = ((man[1][1]<i)?0:((man[1][0]>=i)?(man[1][1]-man[1][0]+1):(man[1][1]-i+1)));
        q = ((man[1][0]>=i)?0:((man[1][1]<i)?(man[1][1]-man[1][0]+1):(i-man[1][0])));
        r = ((man[1][1]<i+1)?0:((man[1][0]>=i+1)?(man[1][1]-man[1][0]+1):(man[1][1]-i)));
        dp[1][0] = q%MD, dp[1][1] = p%MD;
        dp2[1][0] = q%MD, dp2[1][1] = r%MD;
        for(j=2;j<=n;j++){
            p = ((man[j][1]<i)?0:((man[j][0]>=i)?(man[j][1]-man[j][0]+1):(man[j][1]-i+1)));
            q = ((man[j][0]>=i)?0:((man[j][1]<i)?(man[j][1]-man[j][0]+1):(i-man[j][0])));
            r = ((man[j][1]<i+1)?0:((man[j][0]>=i+1)?(man[j][1]-man[j][0]+1):(man[j][1]-i)));
            for(k=0;k<=j && k<ra;k++){
                dp[j][k] = (dp[j-1][k] * q % MD + ((k)?(dp[j-1][k-1] * p % MD):0))%MD;
                dp2[j][k] = (dp2[j-1][k] * q % MD + ((k)?(dp2[j-1][k-1] * r % MD):0))%MD;
            }
        }
        ans += (dp[n][ra-1]-dp2[n][ra-1]);
        while(ans<0) ans += MD;
        ans %= MD;
    }
    ans = all - ans;
    while(ans < 0) ans += MD;
    printf("%lld\n",ans);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2496 KB Output is correct
2 Correct 0 ms 2496 KB Output is correct
3 Correct 0 ms 2496 KB Output is correct
4 Correct 0 ms 2496 KB Output is correct
5 Correct 0 ms 2496 KB Output is correct
6 Correct 0 ms 2496 KB Output is correct
7 Correct 0 ms 2496 KB Output is correct
8 Correct 0 ms 2496 KB Output is correct
9 Correct 0 ms 2496 KB Output is correct
10 Correct 0 ms 2496 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2496 KB Output is correct
2 Correct 0 ms 2496 KB Output is correct
3 Correct 0 ms 2496 KB Output is correct
4 Correct 0 ms 2496 KB Output is correct
5 Correct 0 ms 2496 KB Output is correct
6 Correct 0 ms 2496 KB Output is correct
7 Correct 0 ms 2496 KB Output is correct
8 Correct 0 ms 2496 KB Output is correct
9 Correct 0 ms 2496 KB Output is correct
10 Correct 0 ms 2496 KB Output is correct

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2496 KB Output isn't correct
2 Halted 0 ms 0 KB -