oj.uz

Submission #1076366

# Submission time Handle Problem Language Result Execution time Memory
1076366 2024-08-26T13:19:31 Z alexdd Boat (APIO16_boat) C++17
9 / 100
 2000 ms 3996 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
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 n,cate;
int le[505],ri[505];
map<int,int> mp,nrm;
int invnrm[1005],nr[1005];
int dp[1005][505];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>le[i]>>ri[i];
        mp[le[i]]++;
        mp[ri[i]]++;
    }
    for(auto it:mp)
    {
        if(it.second)
        {
            nrm[it.first]=++cate;
            invnrm[cate]=it.first;
        }
    }
    for(int i=1;i<=cate;i++)
    {
        nr[i] = invnrm[i]-invnrm[i-1];
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        le[i] = nrm[le[i]];
        ri[i] = nrm[ri[i]];
        int copnr = nr[le[i]];
        nr[le[i]]=1;
        for(int ult=ri[i];ult>=le[i];ult--)
        {
            for(int cnt=min(i,nr[ult]);cnt>1;cnt--)
            {
                dp[ult][cnt]= (dp[ult][cnt] + dp[ult][cnt-1] * (nr[ult]-cnt+1)%MOD * put(cnt,MOD-2))%MOD;
            }
            for(int j=0;j<ult;j++)
                for(int orice=0;orice<i;orice++)
                    dp[ult][1] = (dp[ult][1] + dp[j][orice]*nr[ult])%MOD;
        }
        nr[le[i]]=copnr;
    }
    int rez=0;
    for(int ult=1;ult<=cate;ult++)
        for(int cnt=1;cnt<=n;cnt++)
            rez = (rez + dp[ult][cnt])%MOD;
    cout<<rez;
    return 0;
}
/**

impartim intervalul [1,1e9] in intervale relevante, o sa avem maxim 1000 intervale relevante

dp[i][ult][cnt] = in cate moduri pot primele i scoli barci, a.i. ultimele cnt numere sa fie aflate in intervalul ult

daca i poate sa aleaga intervalul ult

dp[i][ult][1] = dp[i-1][ult][1] + sum(dp[i-1][orice<ult][orice])*nr[ult]
pt cnt>=2  dp[i][ult][cnt] = dp[i-1][ult][cnt] + dp[i-1][ult][cnt-1] / comb(nr[ult],cnt-1) * comb(nr[ult],cnt)
pt cnt>=2  dp[i][ult][cnt] = dp[i-1][ult][cnt] + dp[i-1][ult][cnt-1] * (nr[ult]-cnt+1) / cnt

(nr[ult]-cnt+1) / cnt

*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 2492 KB Output is correct
2 Correct 131 ms 2732 KB Output is correct
3 Correct 128 ms 2388 KB Output is correct
4 Correct 126 ms 2480 KB Output is correct
5 Correct 127 ms 2384 KB Output is correct
6 Correct 167 ms 2336 KB Output is correct
7 Correct 171 ms 2388 KB Output is correct
8 Correct 168 ms 2384 KB Output is correct
9 Correct 167 ms 2256 KB Output is correct
10 Correct 167 ms 2392 KB Output is correct
11 Correct 167 ms 2384 KB Output is correct
12 Correct 167 ms 2640 KB Output is correct
13 Correct 168 ms 2256 KB Output is correct
14 Correct 168 ms 2272 KB Output is correct
15 Correct 167 ms 2272 KB Output is correct
16 Correct 18 ms 604 KB Output is correct
17 Correct 19 ms 848 KB Output is correct
18 Correct 19 ms 856 KB Output is correct
19 Correct 19 ms 600 KB Output is correct
20 Correct 19 ms 604 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 2492 KB Output is correct
2 Correct 131 ms 2732 KB Output is correct
3 Correct 128 ms 2388 KB Output is correct
4 Correct 126 ms 2480 KB Output is correct
5 Correct 127 ms 2384 KB Output is correct
6 Correct 167 ms 2336 KB Output is correct
7 Correct 171 ms 2388 KB Output is correct
8 Correct 168 ms 2384 KB Output is correct
9 Correct 167 ms 2256 KB Output is correct
10 Correct 167 ms 2392 KB Output is correct
11 Correct 167 ms 2384 KB Output is correct
12 Correct 167 ms 2640 KB Output is correct
13 Correct 168 ms 2256 KB Output is correct
14 Correct 168 ms 2272 KB Output is correct
15 Correct 167 ms 2272 KB Output is correct
16 Correct 18 ms 604 KB Output is correct
17 Correct 19 ms 848 KB Output is correct
18 Correct 19 ms 856 KB Output is correct
19 Correct 19 ms 600 KB Output is correct
20 Correct 19 ms 604 KB Output is correct
21 Execution timed out 2059 ms 3996 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 2492 KB Output is correct
2 Correct 131 ms 2732 KB Output is correct
3 Correct 128 ms 2388 KB Output is correct
4 Correct 126 ms 2480 KB Output is correct
5 Correct 127 ms 2384 KB Output is correct
6 Correct 167 ms 2336 KB Output is correct
7 Correct 171 ms 2388 KB Output is correct
8 Correct 168 ms 2384 KB Output is correct
9 Correct 167 ms 2256 KB Output is correct
10 Correct 167 ms 2392 KB Output is correct
11 Correct 167 ms 2384 KB Output is correct
12 Correct 167 ms 2640 KB Output is correct
13 Correct 168 ms 2256 KB Output is correct
14 Correct 168 ms 2272 KB Output is correct
15 Correct 167 ms 2272 KB Output is correct
16 Correct 18 ms 604 KB Output is correct
17 Correct 19 ms 848 KB Output is correct
18 Correct 19 ms 856 KB Output is correct
19 Correct 19 ms 600 KB Output is correct
20 Correct 19 ms 604 KB Output is correct
21 Execution timed out 2059 ms 3996 KB Time limit exceeded
22 Halted 0 ms 0 KB -