Submission #113014

#	Time	Username	Problem	Language	Result	Execution time	Memory
113014		MAMBA	Calvinball championship (CEOI15_teams)	C++17	100 / 100	409 ms	732 KiB

teams

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10