제출 #753832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753832		alexdd	Boat (APIO16_boat)	C++17	0 / 100	4 ms	4180 KiB

boat

#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
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42