oj.uz

Submission #113014

# Submission time Handle Problem Language Result Execution time Memory
113014 2019-05-23T06:01:12 Z MAMBA Calvinball championship (CEOI15_teams) C++17
100 / 100
 409 ms 732 KB 
#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<pld> vi;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 1e4 + 10;

constexpr int MOD = 1e6 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

ll dp[2][N]; // dp i , j  => i nafar ke ghable avlin nafar j t ahalat dashtim
				// dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j + 1];

int a[N], b[N], n;

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

#ifndef LOCAL
	//fileIO("superposition");
#endif

	cin >> n;
	rep(i , 0 , n) {
		cin >> a[i];
		b[i + 1] = max(a[i] , b[i]);
	}

	rep(i , 0 , n + 2)
		dp[0][i] = 1;

	ll res = 0;
	rep(i , 1 , n + 1) {
		int id = i & 1;
		memset(dp[id] , 0 , sizeof(dp[0]));
		add(res , (a[n - i] - 1) * dp[id ^ 1][b[n - i]]);
		rep(j , 0 , n + 1) 
			add(dp[id][j] , j * dp[id ^ 1][j] + dp[id ^ 1][j + 1]);

	}	

	cout << res + 1 << endl;

	return 0;

}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 508 KB Output is correct
2 Correct 9 ms 512 KB Output is correct
3 Correct 9 ms 552 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 732 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 584 KB Output is correct
2 Correct 112 ms 600 KB Output is correct
3 Correct 112 ms 640 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 608 KB Output is correct
2 Correct 403 ms 640 KB Output is correct
3 Correct 408 ms 660 KB Output is correct