Submission #527236

# Submission time Handle Problem Language Result Execution time Memory
527236 2022-02-17T04:05:27 Z maomao90 Calvinball championship (CEOI15_teams) C++17
0 / 100
36 ms 65540 KB
    #include <bits/stdc++.h>
    using namespace std;
     
    #define REP(i, j, k) for (int i = j; i < k; i++)
    #define RREP(i, j, k) for (int i = j; i >= k; i--)
     
    template<class T>
    inline bool mxto(T &a, T b) {return a < b ? a = b, 1 : 0;}
    template<class T>
    inline bool mnto(T &a, T b) {return a > b ? a = b, 1 : 0;}
     
    typedef long long ll;
    #define FI first
    #define SE second
    #define MP make_pair
    typedef pair<int, int> ii;
    #define pb push_back
    #define ALL(x) x.begin(), x.end()
    typedef vector<int> vi;
    typedef vector<ii> vii;
     
    #ifndef DEBUG
    #define cerr if (0) cerr
    #endif
     
    #define INF 1000000005
    #define LINF 1000000000000000005ll
    #define MAXN 10005
    #define MOD 1000007
     
    int n;
    int a[MAXN];
     
    int memo[MAXN][MAXN][2];
    int dp(int i, int j, bool same) {
    	if (i >= n) {
    		return 1;
    	}
    	if (memo[i][j][same] != -1) {
    		return memo[i][j][same];
    	}
    	int res = 0;
    	if (same) {
    		REP (k, 1, min(j + 1, a[i])) {
    			res += dp(i + 1, j, 0);
    			if (res >= MOD) {
    				res -= MOD;
    			}
    		}
    		if (a[i] <= j + 1) {
    			res += dp(i + 1, max(j, a[i]), 1);
    			if (res >= MOD) {
    				res -= MOD;
    			}
    		}
    	} else {
    		REP (k, 1, j + 1) {
    			res += dp(i + 1, j, 0);
    			if (res >= MOD) {
    				res -= MOD;
    			}
    		}
    		res += dp(i + 1, j + 1, 0);
    		if (res >= MOD) {
    			res -= MOD;
    		}
    	}
    	return memo[i][j][same] = res;
    }
     
    int main() {
    #ifndef DEBUG
    	ios::sync_with_stdio(0), cin.tie(0);
    #endif
    	cin >> n;
    	REP (i, 0, n) {
    		cin >> a[i];
    	}
    	memset(memo, -1, sizeof memo);
    	cout << dp(0, 0, 1) << '\n';
    	return 0;
    }
# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -