oj.uz

Submission #171672

# Submission time Handle Problem Language Result Execution time Memory
171672 2019-12-29T22:18:37 Z alishahali1382 Calvinball championship (CEOI15_teams) C++14
100 / 100
 213 ms 764 KB 
#include <bits/stdc++.h>
#if defined(__GNUC__)
#pragma GCC optimize ("Ofast")
#endif
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000007;
const int MAXN = 10010, LOG=20;

ll n, m, k, u, v, x, y, t, ans;
int A[MAXN], B[MAXN];
ll dp[2][MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<=n; i++) cin>>A[i], B[i]=max(B[i-1], A[i]);
	
	int a=0, b=1;
	for (int j=0; j<=n; j++) dp[a][j]=1;
	for (int i=0; i<n; i++){
		ans+=dp[a][B[n-i-1]]*(A[n-i]-1);
		for (int j=0; j<=n; j++) dp[b][j]=(dp[a][j]*j + dp[a][j+1])%mod;
		swap(a, b);
	}
	ans++;
	cout<<ans%mod<<'\n';
		
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 764 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 532 KB Output is correct
2 Correct 55 ms 508 KB Output is correct
3 Correct 55 ms 524 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 648 KB Output is correct
2 Correct 213 ms 644 KB Output is correct
3 Correct 212 ms 700 KB Output is correct