oj.uz

답안 #753832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753832 2023-06-06T07:04:08 Z alexdd Boat (APIO16_boat) C++17
0 / 100
 4 ms 4180 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int n;
int dp[505][1005];
int a[505];
int b[505];
int nr[1005];
int put(int a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put((a*a)%MOD,exp/2);
    else
        return (put((a*a)%MOD,exp/2)*a)%MOD;
}
int famod(int x)
{
    if(x>=MOD)
        x-=MOD;
    return x;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        nr[(i-1)*2 + 1] = a[i];
        nr[(i-1)*2 + 2] = b[i];
    }
    sort(nr+1,nr+1+2*n);
    int put2=put(2,MOD-2);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=2*n;j++)
        {
            if(a[i] <= nr[j-1]+1 && nr[j] <= b[i])
            {
                dp[i][j] = famod(dp[i-1][j] + (dp[i-1][j] * (nr[j]-nr[j-1]-1) * put2)%MOD);
                for(int orice=1;orice<j;orice++)
                    dp[i][j] = famod(dp[i][j] + (dp[i-1][orice] * (nr[j]-nr[j-1]))%MOD);
                dp[i][j] = famod(dp[i][j] + (nr[j]-nr[j-1]));
            }
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    int rez=0;
    for(int j=1;j<=2*n;j++)
        rez = famod(rez+dp[n][j]);
    cout<<rez;
    return 0;
}
/**

dp[i][j] = numarul de moduri pentru primele i scoli ca sa trimita barci a.i. maximul de barci trimise sa fie j

auxdp[i][j] = sum(dp[i][x]), x = nr[j-1] + 1 ... nr[j]

prec:                                                      0                   prec <= nr[j-1]                       nr[j-1] < prec <= nr[j]
if(a[i] <= nr[j-1]+1 && nr[j] <= b[i]) auxdp[i][j] = auxdp[i-1][j] + sum(auxdp[i-1][orice<j] * (nr[j]-nr[j-1])) + auxdp[i-1][j] * (nr[j]-nr[j-1]-1)/2
else                                   auxdp[i][j] = auxdp[i-1][j]

*/

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -