oj.uz

Submission #124068

# Submission time Handle Problem Language Result Execution time Memory
124068 2019-07-02T13:10:02 Z Mtaylor Boat (APIO16_boat) C++17
9 / 100
 2000 ms 16732 KB 
#include <bits/stdc++.h>
 
    using namespace std;
    typedef long long ll;
    typedef vector<ll> vl ;
 
    #define mp make_pair
    #define pb push_back
    #define f first
    #define s second
    #define all(v) (v).begin(),(v).end()
 
 
    const int MOD = 1000000007;
    const int N = 1000005;
    const double PI =4*atan(1);
    const double eps = 1e-7;
 
    map<ll,ll> maa;
    map<ll,ll> mal;
    ll n;
    set<ll> ss;
    ll c[N];
    ll d[N];
    ll b[N];
    ll a[N];
    ll dp[505][4005];

    ll solve(ll pos , ll prev){
        if(pos>=n  && prev==0)return 0;
        //cout << pos << " " << prev << endl;
        if(pos>=n)return 1;
        //cout << "trol"<< endl;
        ll to_return =solve(pos+1,prev);
        if(dp[pos][prev]>=0)return dp[pos][prev];
        ll x=max(c[pos],prev);
        //cout << mal[x] << endl;
        ll z=mal[x]-1;
        for(int i=x;i<=d[pos];i++){
        	//cout << pos << " " <<mal[i] << " " << z<< endl;
        	ll y=maa[mal[i]+1];
        	//cout << y<<" " << mal[y]<<endl;
            to_return += ((mal[i]-z)%MOD )* (solve(pos+1, y)%MOD) %MOD ;
            z=mal[i];
            to_return %=MOD;
        }
        return dp[pos][prev]=to_return;
    }
 
 
    int main(){
        ios::sync_with_stdio(0);
        //freopen("easy.txt","r",stdin);
        memset(dp,-1,sizeof(dp));
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> a[i];
            cin >> b[i];
            ss.insert(a[i]);
            ss.insert(a[i]-1);
            ss.insert(a[i]+1);
            ss.insert(b[i]+1);
            ss.insert(b[i]-1);
            ss.insert(b[i]);
        }
        ll cnt=1;
        maa[0]=0;
        mal[0]=0;
        for(auto t:ss){
            maa[t]=cnt;
            mal[cnt]=t;
            cnt++;
        }
        for(int i=0;i<n;i++){
            c[i]=maa[a[i]];
            d[i]=maa[b[i]];
        }
        ll ans = solve(0,0);
        cout << ans;


        return 0;
    }

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 16504 KB Output is correct
2 Correct 182 ms 16592 KB Output is correct
3 Correct 186 ms 16632 KB Output is correct
4 Correct 186 ms 16504 KB Output is correct
5 Correct 185 ms 16636 KB Output is correct
6 Correct 292 ms 16592 KB Output is correct
7 Correct 299 ms 16504 KB Output is correct
8 Correct 300 ms 16636 KB Output is correct
9 Correct 305 ms 16504 KB Output is correct
10 Correct 305 ms 16508 KB Output is correct
11 Correct 292 ms 16504 KB Output is correct
12 Correct 287 ms 16632 KB Output is correct
13 Correct 294 ms 16504 KB Output is correct
14 Correct 295 ms 16632 KB Output is correct
15 Correct 289 ms 16636 KB Output is correct
16 Correct 56 ms 16376 KB Output is correct
17 Correct 56 ms 16376 KB Output is correct
18 Correct 58 ms 16380 KB Output is correct
19 Correct 55 ms 16376 KB Output is correct
20 Correct 55 ms 16376 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 16504 KB Output is correct
2 Correct 182 ms 16592 KB Output is correct
3 Correct 186 ms 16632 KB Output is correct
4 Correct 186 ms 16504 KB Output is correct
5 Correct 185 ms 16636 KB Output is correct
6 Correct 292 ms 16592 KB Output is correct
7 Correct 299 ms 16504 KB Output is correct
8 Correct 300 ms 16636 KB Output is correct
9 Correct 305 ms 16504 KB Output is correct
10 Correct 305 ms 16508 KB Output is correct
11 Correct 292 ms 16504 KB Output is correct
12 Correct 287 ms 16632 KB Output is correct
13 Correct 294 ms 16504 KB Output is correct
14 Correct 295 ms 16632 KB Output is correct
15 Correct 289 ms 16636 KB Output is correct
16 Correct 56 ms 16376 KB Output is correct
17 Correct 56 ms 16376 KB Output is correct
18 Correct 58 ms 16380 KB Output is correct
19 Correct 55 ms 16376 KB Output is correct
20 Correct 55 ms 16376 KB Output is correct
21 Execution timed out 2037 ms 16732 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 16376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 16504 KB Output is correct
2 Correct 182 ms 16592 KB Output is correct
3 Correct 186 ms 16632 KB Output is correct
4 Correct 186 ms 16504 KB Output is correct
5 Correct 185 ms 16636 KB Output is correct
6 Correct 292 ms 16592 KB Output is correct
7 Correct 299 ms 16504 KB Output is correct
8 Correct 300 ms 16636 KB Output is correct
9 Correct 305 ms 16504 KB Output is correct
10 Correct 305 ms 16508 KB Output is correct
11 Correct 292 ms 16504 KB Output is correct
12 Correct 287 ms 16632 KB Output is correct
13 Correct 294 ms 16504 KB Output is correct
14 Correct 295 ms 16632 KB Output is correct
15 Correct 289 ms 16636 KB Output is correct
16 Correct 56 ms 16376 KB Output is correct
17 Correct 56 ms 16376 KB Output is correct
18 Correct 58 ms 16380 KB Output is correct
19 Correct 55 ms 16376 KB Output is correct
20 Correct 55 ms 16376 KB Output is correct
21 Execution timed out 2037 ms 16732 KB Time limit exceeded
22 Halted 0 ms 0 KB -