oj.uz

Submission #518473

# Submission time Handle Problem Language Result Execution time Memory
518473 2022-01-23T21:40:31 Z julian33 Boat (APIO16_boat) C++14
9 / 100
 1766 ms 4388 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=2e5+5; //make sure this is right
const int mod=1e9+7;

struct RANK{
    vector<int> all;
    int get(int x){return lower_bound(all.begin(),all.end(),x)-all.begin()+1;}
    void add(int x){all.pb(x);}
    void fix(){
        sort(all.begin(),all.end());
        all.resize(unique(all.begin(),all.end())-all.begin());
    }  
} rnk;

ll dp[505][1005],a[505],b[505];

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    rnk.add(1);
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        rnk.add(a[i]);
        rnk.add(b[i]);
        rnk.add(b[i]+1);
    }
    rnk.fix();
    dp[0][1]=1;
    for(int i=1;i<=n;i++){
        int A=a[i]; int B=b[i];
        for(int j=1;j<=sz(rnk.all);j++){
            ll ways=min(B,rnk.all[j-1]-1)-max(A,j==1?1:rnk.all[j-2])+1;
            maxa(ways,0LL);
            dp[i][j]=dp[i-1][j];
            for(int k=j-1;k>=1;k--){
                dp[i][j]+=(dp[i-1][k]*ways)%mod;
                dp[i][j]%=mod;
            }
        }
    }
    ll ans=0;
    for(int i=2;i<=sz(rnk.all);i++)
        ans=(ans+dp[n][i])%mod;
    cout<<ans<<"\n";
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 4168 KB Output is correct
2 Correct 1052 ms 4184 KB Output is correct
3 Correct 1046 ms 4240 KB Output is correct
4 Correct 1030 ms 4368 KB Output is correct
5 Correct 1064 ms 4328 KB Output is correct
6 Correct 1047 ms 4240 KB Output is correct
7 Correct 1038 ms 4188 KB Output is correct
8 Correct 1055 ms 4220 KB Output is correct
9 Correct 1040 ms 4248 KB Output is correct
10 Correct 1053 ms 4256 KB Output is correct
11 Correct 1036 ms 4352 KB Output is correct
12 Correct 1030 ms 4388 KB Output is correct
13 Correct 1040 ms 4244 KB Output is correct
14 Correct 1033 ms 4304 KB Output is correct
15 Correct 1063 ms 4256 KB Output is correct
16 Correct 33 ms 3016 KB Output is correct
17 Correct 40 ms 3000 KB Output is correct
18 Correct 36 ms 2992 KB Output is correct
19 Correct 40 ms 3076 KB Output is correct
20 Correct 37 ms 3016 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 4168 KB Output is correct
2 Correct 1052 ms 4184 KB Output is correct
3 Correct 1046 ms 4240 KB Output is correct
4 Correct 1030 ms 4368 KB Output is correct
5 Correct 1064 ms 4328 KB Output is correct
6 Correct 1047 ms 4240 KB Output is correct
7 Correct 1038 ms 4188 KB Output is correct
8 Correct 1055 ms 4220 KB Output is correct
9 Correct 1040 ms 4248 KB Output is correct
10 Correct 1053 ms 4256 KB Output is correct
11 Correct 1036 ms 4352 KB Output is correct
12 Correct 1030 ms 4388 KB Output is correct
13 Correct 1040 ms 4244 KB Output is correct
14 Correct 1033 ms 4304 KB Output is correct
15 Correct 1063 ms 4256 KB Output is correct
16 Correct 33 ms 3016 KB Output is correct
17 Correct 40 ms 3000 KB Output is correct
18 Correct 36 ms 2992 KB Output is correct
19 Correct 40 ms 3076 KB Output is correct
20 Correct 37 ms 3016 KB Output is correct
21 Incorrect 1766 ms 4244 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 4168 KB Output is correct
2 Correct 1052 ms 4184 KB Output is correct
3 Correct 1046 ms 4240 KB Output is correct
4 Correct 1030 ms 4368 KB Output is correct
5 Correct 1064 ms 4328 KB Output is correct
6 Correct 1047 ms 4240 KB Output is correct
7 Correct 1038 ms 4188 KB Output is correct
8 Correct 1055 ms 4220 KB Output is correct
9 Correct 1040 ms 4248 KB Output is correct
10 Correct 1053 ms 4256 KB Output is correct
11 Correct 1036 ms 4352 KB Output is correct
12 Correct 1030 ms 4388 KB Output is correct
13 Correct 1040 ms 4244 KB Output is correct
14 Correct 1033 ms 4304 KB Output is correct
15 Correct 1063 ms 4256 KB Output is correct
16 Correct 33 ms 3016 KB Output is correct
17 Correct 40 ms 3000 KB Output is correct
18 Correct 36 ms 2992 KB Output is correct
19 Correct 40 ms 3076 KB Output is correct
20 Correct 37 ms 3016 KB Output is correct
21 Incorrect 1766 ms 4244 KB Output isn't correct
22 Halted 0 ms 0 KB -