oj.uz

답안 #361903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361903 2021-02-01T02:33:54 Z HuyQuang_re_Zero Boat (APIO16_boat) C++14
0 / 100
 171 ms 164960 KB 
#include <bits/stdc++.h>
#define N 502
using namespace std;
struct pt { int l,r; };
pt a[N],b[N];
long long f[101][1001][101],g[101][1001][101],ng[N],i,j,k,n,m,sl[N];
const int mod=round(1e9)+7;
void nenso()
{
    set <int> s;
    for(i=1;i<=n;i++) { s.insert(a[i].l); s.insert(a[i].r); }
    int tr;
    for(set <int>::iterator it=s.begin();it!=s.end();it++)
    {
        if(it==s.begin()) b[++m]={ (*it),(*it) };
        else
        {
            b[++m]={ tr+1,(*it) };
            sl[m]=b[m].r-b[m].l+1;
        }
        sl[m]=b[m].r-b[m].l+1;
        tr=(*it);
    }
}
long long lt(long long a,long long b)
{
    if(b==0) return 1;
    long long tg=lt(a,b/2);
    if(b%2==0) return tg*tg%mod;
    return tg*tg%mod*a%mod;
}
int main()
{
   // freopen("boat.inp","r",stdin);
  //  freopen("boat.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
    nenso();

    for(i=n;i>=0;i--)
    {
        ng[i]=lt(i,mod-2);
     //   cerr<<ng[i]<<'\n';
    }
    for(j=0;j<=m;j++) g[0][j][0]=f[0][j][0]=1;
    for(i=1;i<=n;i++)
        for(j=0;j<=m;j++)
        {
            for(k=0;k<=min(i,sl[j]);k++)
            {
                if(k==0)
                {
                    if(j>0)
                    {
                        f[i][j][k]=g[i][j-1][min(i,sl[j-1])];
                    //    cerr<<j-1<<" "<<min(i,sl[j-1])<<" "<<g[i][j-1][min(i,sl[j-1])]<<'\n';
                    }
                    else f[i][j][k]=1;
                    g[i][j][k]=f[i][j][k];
                }
                else
                {
                    f[i][j][k]=f[i-1][j][k];
                    if(a[i].l<=b[j].l && b[j].r<=a[i].r)
                    {
                        f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*(sl[j]-k+1)%mod*ng[k])%mod;
                       // cerr<<i<<" "<<j<<" "<<k<<" "<<f[i-1][j][k-1]<<'\n';
                    }
                    g[i][j][k]=g[i][j][k-1]+f[i][j][k];
                    if(g[i][j][k]>=mod) g[i][j][k]-=mod;
                }
              //  cerr<<i<<" "<<j<<" "<<k<<" "<<f[i][j][k]<<'\n';
            }
        }
    cout<<(g[n][m][min(n,sl[m])]-1+mod)%mod;
}

Compilation message

boat.cpp: In function 'void nenso()':
boat.cpp:18:24: warning: 'tr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   18 |             b[++m]={ tr+1,(*it) };
      |                      ~~^~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 171 ms 164960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 171 ms 164960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 171 ms 164960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -