oj.uz

Submission #242962

# Submission time Handle Problem Language Result Execution time Memory
242962 2020-06-30T02:45:41 Z Lawliet Calvinball championship (CEOI15_teams) C++17
100 / 100
 217 ms 760 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 10010;
const int MOD = 1000007;

int n;

int v[MAXN];
int mxPrefix[MAXN];

lli dp[2][MAXN];

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

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

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

	for(int i = 1 ; i <= n ; i++)
		mxPrefix[i] = max( mxPrefix[i - 1] , v[i] );

	lli ans = 0;

	for(int i = n ; i > 0 ; i--)
	{
		ans += dp[ (i + 1)%2 ][ mxPrefix[i - 1] ]*( v[i] - 1 );
		ans %= MOD;

		for(int j = 0 ; j <= n ; j++)
		{
			lli& curDp = dp[i%2][j];

			curDp = dp[ (i + 1)%2 ][j]*j;
			curDp += dp[ (i + 1)%2 ][j + 1];

			curDp %= MOD;
		}
	}

	ans++;
	ans %= MOD;

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

Compilation message

teams.cpp: In function 'int main()':
teams.cpp:50:19: warning: format '%d' expects argument of type 'int', but argument 2 has type 'lli {aka long long int}' [-Wformat=]
  printf("%d\n",ans);
                   ^
teams.cpp:18: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",&v[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 640 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 632 KB Output is correct
2 Correct 217 ms 512 KB Output is correct
3 Correct 211 ms 760 KB Output is correct