oj.uz

Submission #399332

# Submission time Handle Problem Language Result Execution time Memory
399332 2021-05-05T15:13:03 Z jeqcho Boat (APIO16_boat) C++17
31 / 100
 2000 ms 279392 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

// subtask 1

int const N=5e2+3;
int a[N],b[N];
int const D=1e6+3;
ll dp[D];
ll mod =1e9+7;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin>>n;
	set<int> st;
	F0R(i,n)
	{
		cin>>a[i]>>b[i];
		FOR(j,a[i],b[i]+1)
		{
			st.insert(j);
		}
	}
	vi v(all(st));
	map<int,int>mp;
	F0R(i,sz(st))
	{
		mp[v[i]]=i+1;
	}
	F0R(i,n)
	{
		a[i]=mp[a[i]];
		b[i]=mp[b[i]];
	}
	F0R(j,sz(st)+1)
	{
		dp[j]=0;
	}
	dp[0]=1;
	F0R(i,n)
	{
		ll sum=0;
		F0R(j,b[i]+1)
		{
			ll temp = dp[j];
			if(j>=a[i])
			{
				dp[j]+=sum;
				dp[j]%=mod;
			}
			sum += temp;
			sum%=mod;
		}
	}
	ll ans=0;
	FOR(j,1,sz(st)+1)
	{
		ans+=dp[j];
		ans%=mod;
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 56 ms 808 KB Output is correct
22 Correct 56 ms 808 KB Output is correct
23 Correct 54 ms 824 KB Output is correct
24 Correct 57 ms 816 KB Output is correct
25 Correct 62 ms 820 KB Output is correct
26 Correct 51 ms 608 KB Output is correct
27 Correct 52 ms 628 KB Output is correct
28 Correct 52 ms 612 KB Output is correct
29 Correct 52 ms 708 KB Output is correct
30 Correct 1441 ms 104708 KB Output is correct
31 Correct 1397 ms 102844 KB Output is correct
32 Correct 1460 ms 104776 KB Output is correct
33 Correct 1434 ms 102084 KB Output is correct
34 Correct 1457 ms 103044 KB Output is correct
35 Correct 1320 ms 98340 KB Output is correct
36 Correct 1329 ms 101800 KB Output is correct
37 Correct 1379 ms 102824 KB Output is correct
38 Correct 1332 ms 99480 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 56 ms 808 KB Output is correct
22 Correct 56 ms 808 KB Output is correct
23 Correct 54 ms 824 KB Output is correct
24 Correct 57 ms 816 KB Output is correct
25 Correct 62 ms 820 KB Output is correct
26 Correct 51 ms 608 KB Output is correct
27 Correct 52 ms 628 KB Output is correct
28 Correct 52 ms 612 KB Output is correct
29 Correct 52 ms 708 KB Output is correct
30 Correct 1441 ms 104708 KB Output is correct
31 Correct 1397 ms 102844 KB Output is correct
32 Correct 1460 ms 104776 KB Output is correct
33 Correct 1434 ms 102084 KB Output is correct
34 Correct 1457 ms 103044 KB Output is correct
35 Correct 1320 ms 98340 KB Output is correct
36 Correct 1329 ms 101800 KB Output is correct
37 Correct 1379 ms 102824 KB Output is correct
38 Correct 1332 ms 99480 KB Output is correct
39 Execution timed out 2088 ms 279392 KB Time limit exceeded
40 Halted 0 ms 0 KB -