oj.uz

Submission #259435

# Submission time Handle Problem Language Result Execution time Memory
259435 2020-08-07T20:03:33 Z ChrisT Calvinball championship (CEOI15_teams) C++17
100 / 100
 127 ms 564 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int MN = 1e4 + 5, LOG = 18, MOD = 1e6 + 7;
int dp2[2][MN], a[MN], mx[MN];
int main () {
	int n, ans = 1;
	scanf ("%d",&n);
	for (int i = 1; i <= n; i++) scanf ("%d",&a[i]), mx[i] = max(mx[i-1],a[i-1]);
	for (int j = 1; j <= n; j++) dp2[n&1][j] = 1;
	for (int i = n; i >= 1; i--) {
		if (i<n)
		for (int j = 1; j <= i; j++) {
			dp2[i&1][j] = (dp2[i&1^1][j+1] + (ll)dp2[i&1^1][j] * j) % MOD;
		}
		ans = (ans + (ll)(a[i]-1)*dp2[i&1][mx[i]]) % MOD;
	}
	printf ("%d\n",ans);
	return 0;
}

Compilation message

teams.cpp: In function 'int main()':
teams.cpp:15:24: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    dp2[i&1][j] = (dp2[i&1^1][j+1] + (ll)dp2[i&1^1][j] * j) % MOD;
                       ~^~
teams.cpp:15:46: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    dp2[i&1][j] = (dp2[i&1^1][j+1] + (ll)dp2[i&1^1][j] * j) % MOD;
                                             ~^~
teams.cpp:9:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&n);
  ~~~~~~^~~~~~~~~
teams.cpp:10:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf ("%d",&a[i]), mx[i] = max(mx[i-1],a[i-1]);
                               ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 564 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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