oj.uz

Submission #107821

# Submission time Handle Problem Language Result Execution time Memory
107821 2019-04-26T00:06:59 Z luciocf Calvinball championship (CEOI15_teams) C++14
100 / 100
 597 ms 576 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4+10;
const int mod = 1e6+7;

int a[maxn];

int dp[2][maxn], mx[maxn];

void add(int &a, int b)
{
	a = (a+b)%mod;
}

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);

		mx[i] = max(mx[i-1], a[i]);
	}

	for (int i = 1; i <= n; i++) dp[0][i] = 1;

	int ans = 1;
	for (int i = n-1; i >= 1; i--)
	{
		int cur = (n-i)%2, prev = (n-i-1)%2;

		for (int j = 1; j <= n; j++)
		{
			dp[cur][j] = 0;

			add(dp[cur][j], (1ll*j*dp[prev][j])%mod);
			add(dp[cur][j], dp[prev][j+1]);
		}


		for (int j = a[i]-1; j >= 1; j--)
			add(ans, dp[cur][max(mx[i-1], j)]);
	}

	add(ans, a[n]-1);

	printf("%d\n", ans);
}

Compilation message

teams.cpp: In function 'int main()':
teams.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
teams.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 384 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 3 ms 356 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 568 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 504 KB Output is correct
2 Correct 102 ms 464 KB Output is correct
3 Correct 148 ms 480 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 540 KB Output is correct
2 Correct 415 ms 576 KB Output is correct
3 Correct 569 ms 512 KB Output is correct