oj.uz

Submission #1092839

# Submission time Handle Problem Language Result Execution time Memory
1092839 2024-09-25T08:35:42 Z alexander707070 Boat (APIO16_boat) C++14
9 / 100
 1278 ms 29388 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#define MAXN 5007
using namespace std;
 
struct group{
    int from,to;
}s[2*MAXN];
 
const long long mod=1e9+7;
 
int n,a[MAXN],b[MAXN],m;
vector<int> pos;
 
bool in(group g,int id){
    return g.from>=a[id] and g.to<=b[id];
}
 
long long dp[2][MAXN][507][2];
long long invfact[MAXN];

long long cc[507][MAXN];
 
long long comb(int x,int g){
    return cc[x][g];
}
 
long long power(long long a,int b){
    if(b==0)return 1;
    if(b==1)return a;
    if(b==2)return (a*a)%mod;
    if(b%2==0)return power(power(a,b/2),2);
    return (a*power(power(a,b/2),2));
}
 
 
int main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin>>n;
 
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
 
        pos.push_back(a[i]);
        pos.push_back(b[i]);
    }
 
    invfact[0]=1;
    for(int i=1;i<=n;i++)invfact[i]=(invfact[i-1]*i)%mod;
    for(int i=1;i<=n;i++)invfact[i]=power(invfact[i],mod-2);
 
    sort(pos.begin(),pos.end());
    
    for(int i=0;i<pos.size()-1;i++){
        if(pos[i]!=pos[i+1]){
            m++; s[m]={pos[i],pos[i]};
            
            if(pos[i]+1<=pos[i+1]-1){
                m++; s[m]={pos[i]+1,pos[i+1]-1};
            }
        }
    }
 
    m++;
    s[m]={pos.back(),pos.back()};

    for(int i=1;i<=m;i++){
        cc[0][i]=1;
        for(int f=1;f<=min(n,s[i].to-s[i].from+1);f++){
            cc[f][i]=(long long) cc[f-1][i]*(s[i].to-s[i].from+1-(f-1));
            cc[f][i]%=mod;
        }

        for(int f=1;f<=min(n,s[i].to-s[i].from+1);f++){
            cc[f][i]*=invfact[f];
            cc[f][i]%=mod;
        }
    }

    for(int i=0;i<=m;i++){
        for(int c=0;c<=n;c++){
            if(i==0)dp[0][i][c][1]=1;
            else dp[0][i][c][1]=comb(c,i);
        }
    }

    for(int i=1;i<=n;i++){
        dp[i%2][0][0][1]=1;

        for(int f=1;f<=m;f++){
            for(int c=0;c<=n;c++){
                for(int t=0;t<2;t++){
                    
                    dp[i%2][f][c][t]=dp[1-i%2][f][c][0];
                    if(t==1)dp[i%2][f][c][t]+=dp[i%2][f-1][0][1]*comb(c,f);

                    if(in(s[f],i) and c+1<=s[f].to-s[f].from+1){
                        dp[i%2][f][c][t]+=dp[1-i%2][f][c+1][1];
                    }
    
                    dp[i%2][f][c][t]%=mod;
                }
            }
        }
    }
    
    cout<<(dp[n%2][m][0][1]-1+mod)%mod<<"\n";
 
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<pos.size()-1;i++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 22104 KB Output is correct
2 Correct 839 ms 22312 KB Output is correct
3 Correct 783 ms 22104 KB Output is correct
4 Correct 780 ms 22316 KB Output is correct
5 Correct 783 ms 22312 KB Output is correct
6 Correct 801 ms 22312 KB Output is correct
7 Correct 764 ms 22316 KB Output is correct
8 Correct 800 ms 22112 KB Output is correct
9 Correct 779 ms 22108 KB Output is correct
10 Correct 789 ms 22320 KB Output is correct
11 Correct 755 ms 22104 KB Output is correct
12 Correct 773 ms 22104 KB Output is correct
13 Correct 803 ms 22312 KB Output is correct
14 Correct 788 ms 22108 KB Output is correct
15 Correct 793 ms 22316 KB Output is correct
16 Correct 135 ms 6000 KB Output is correct
17 Correct 140 ms 6236 KB Output is correct
18 Correct 133 ms 5980 KB Output is correct
19 Correct 142 ms 6236 KB Output is correct
20 Correct 135 ms 6228 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 22104 KB Output is correct
2 Correct 839 ms 22312 KB Output is correct
3 Correct 783 ms 22104 KB Output is correct
4 Correct 780 ms 22316 KB Output is correct
5 Correct 783 ms 22312 KB Output is correct
6 Correct 801 ms 22312 KB Output is correct
7 Correct 764 ms 22316 KB Output is correct
8 Correct 800 ms 22112 KB Output is correct
9 Correct 779 ms 22108 KB Output is correct
10 Correct 789 ms 22320 KB Output is correct
11 Correct 755 ms 22104 KB Output is correct
12 Correct 773 ms 22104 KB Output is correct
13 Correct 803 ms 22312 KB Output is correct
14 Correct 788 ms 22108 KB Output is correct
15 Correct 793 ms 22316 KB Output is correct
16 Correct 135 ms 6000 KB Output is correct
17 Correct 140 ms 6236 KB Output is correct
18 Correct 133 ms 5980 KB Output is correct
19 Correct 142 ms 6236 KB Output is correct
20 Correct 135 ms 6228 KB Output is correct
21 Incorrect 1278 ms 29388 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 22104 KB Output is correct
2 Correct 839 ms 22312 KB Output is correct
3 Correct 783 ms 22104 KB Output is correct
4 Correct 780 ms 22316 KB Output is correct
5 Correct 783 ms 22312 KB Output is correct
6 Correct 801 ms 22312 KB Output is correct
7 Correct 764 ms 22316 KB Output is correct
8 Correct 800 ms 22112 KB Output is correct
9 Correct 779 ms 22108 KB Output is correct
10 Correct 789 ms 22320 KB Output is correct
11 Correct 755 ms 22104 KB Output is correct
12 Correct 773 ms 22104 KB Output is correct
13 Correct 803 ms 22312 KB Output is correct
14 Correct 788 ms 22108 KB Output is correct
15 Correct 793 ms 22316 KB Output is correct
16 Correct 135 ms 6000 KB Output is correct
17 Correct 140 ms 6236 KB Output is correct
18 Correct 133 ms 5980 KB Output is correct
19 Correct 142 ms 6236 KB Output is correct
20 Correct 135 ms 6228 KB Output is correct
21 Incorrect 1278 ms 29388 KB Output isn't correct
22 Halted 0 ms 0 KB -