oj.uz

Submission #1076377

# Submission time Handle Problem Language Result Execution time Memory
1076377 2024-08-26T13:24:24 Z alexdd Boat (APIO16_boat) C++17
36 / 100
 2000 ms 7392 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
const int MAXV = 2000;
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[MAXV+5],nr[MAXV+5];
int dp[MAXV+5][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;

            cate++;
            invnrm[cate]=-1;
        }
    }
    for(int i=1;i<=cate;i+=2)
    {
        nr[i]=1;
        nr[i+1]=invnrm[i+2]-invnrm[i]-1;
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        le[i] = nrm[le[i]];
        ri[i] = nrm[ri[i]];
        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;
        }
    }
    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 266 ms 2532 KB Output is correct
2 Correct 265 ms 2428 KB Output is correct
3 Correct 258 ms 2468 KB Output is correct
4 Correct 254 ms 2472 KB Output is correct
5 Correct 264 ms 2380 KB Output is correct
6 Correct 345 ms 2516 KB Output is correct
7 Correct 344 ms 2352 KB Output is correct
8 Correct 337 ms 2532 KB Output is correct
9 Correct 341 ms 2448 KB Output is correct
10 Correct 342 ms 2380 KB Output is correct
11 Correct 348 ms 2416 KB Output is correct
12 Correct 339 ms 2312 KB Output is correct
13 Correct 341 ms 2284 KB Output is correct
14 Correct 344 ms 2320 KB Output is correct
15 Correct 347 ms 2428 KB Output is correct
16 Correct 35 ms 640 KB Output is correct
17 Correct 36 ms 848 KB Output is correct
18 Correct 37 ms 824 KB Output is correct
19 Correct 35 ms 796 KB Output is correct
20 Correct 40 ms 816 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 2532 KB Output is correct
2 Correct 265 ms 2428 KB Output is correct
3 Correct 258 ms 2468 KB Output is correct
4 Correct 254 ms 2472 KB Output is correct
5 Correct 264 ms 2380 KB Output is correct
6 Correct 345 ms 2516 KB Output is correct
7 Correct 344 ms 2352 KB Output is correct
8 Correct 337 ms 2532 KB Output is correct
9 Correct 341 ms 2448 KB Output is correct
10 Correct 342 ms 2380 KB Output is correct
11 Correct 348 ms 2416 KB Output is correct
12 Correct 339 ms 2312 KB Output is correct
13 Correct 341 ms 2284 KB Output is correct
14 Correct 344 ms 2320 KB Output is correct
15 Correct 347 ms 2428 KB Output is correct
16 Correct 35 ms 640 KB Output is correct
17 Correct 36 ms 848 KB Output is correct
18 Correct 37 ms 824 KB Output is correct
19 Correct 35 ms 796 KB Output is correct
20 Correct 40 ms 816 KB Output is correct
21 Execution timed out 2057 ms 7392 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 2024 KB Output is correct
2 Correct 507 ms 1948 KB Output is correct
3 Correct 567 ms 2036 KB Output is correct
4 Correct 592 ms 2036 KB Output is correct
5 Correct 648 ms 2032 KB Output is correct
6 Correct 980 ms 1968 KB Output is correct
7 Correct 978 ms 2220 KB Output is correct
8 Correct 971 ms 1996 KB Output is correct
9 Correct 982 ms 2016 KB Output is correct
10 Correct 992 ms 2036 KB Output is correct
11 Correct 624 ms 2040 KB Output is correct
12 Correct 481 ms 2036 KB Output is correct
13 Correct 490 ms 2044 KB Output is correct
14 Correct 538 ms 1884 KB Output is correct
15 Correct 593 ms 2040 KB Output is correct
16 Correct 123 ms 1136 KB Output is correct
17 Correct 114 ms 1132 KB Output is correct
18 Correct 122 ms 1144 KB Output is correct
19 Correct 115 ms 1116 KB Output is correct
20 Correct 138 ms 1164 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 2532 KB Output is correct
2 Correct 265 ms 2428 KB Output is correct
3 Correct 258 ms 2468 KB Output is correct
4 Correct 254 ms 2472 KB Output is correct
5 Correct 264 ms 2380 KB Output is correct
6 Correct 345 ms 2516 KB Output is correct
7 Correct 344 ms 2352 KB Output is correct
8 Correct 337 ms 2532 KB Output is correct
9 Correct 341 ms 2448 KB Output is correct
10 Correct 342 ms 2380 KB Output is correct
11 Correct 348 ms 2416 KB Output is correct
12 Correct 339 ms 2312 KB Output is correct
13 Correct 341 ms 2284 KB Output is correct
14 Correct 344 ms 2320 KB Output is correct
15 Correct 347 ms 2428 KB Output is correct
16 Correct 35 ms 640 KB Output is correct
17 Correct 36 ms 848 KB Output is correct
18 Correct 37 ms 824 KB Output is correct
19 Correct 35 ms 796 KB Output is correct
20 Correct 40 ms 816 KB Output is correct
21 Execution timed out 2057 ms 7392 KB Time limit exceeded
22 Halted 0 ms 0 KB -