oj.uz

Submission #316564

# Submission time Handle Problem Language Result Execution time Memory
316564 2020-10-26T16:40:19 Z CaroLinda Calvinball championship (CEOI15_teams) C++14
100 / 100
 322 ms 640 KB 
#include <bits/stdc++.h>
 
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
 
const ll MOD = 1e6+7 ;
const int MAXN = 1e4+10 ;
 
using namespace std ;
 
int seq[MAXN] , pref[MAXN] ;
long long dp[2][MAXN] ;
 
int main()
{
 
	int n ;
	scanf("%d", &n ) ;
	for(int i = 1 ; i <= n ; i++ ) 
	{
		scanf("%d", &seq[i]) ;
		
		pref[i] = seq[i] ;
		if(pref[i-1] > pref[i]) pref[i] = pref[i-1] ;
	}
 
	for(int i = 1 ; i <= n ; i++ ) dp[0][i] = 1 ;
 
	int toFill = 1 ;
	long long ans = 1 ;
 
	for(int tam = 0 ; tam < n ; tam++ , toFill = !toFill )
	{
 
		//idx is the place that gives me a suffix of size tam
		int idx = n - tam ;
		long long toSum = dp[!toFill][ pref[idx-1] ] * (ll)(seq[idx]-1) ;
 
		ans += toSum % MOD ;
 
		if(ans >= MOD) ans -= MOD ;
 
		for(int conhecidos = n ; conhecidos >= 0 ; conhecidos-- )
		{
			ll &ptr = dp[toFill][conhecidos];
 
			ptr = ( (ll)conhecidos * dp[!toFill][conhecidos] ) % MOD ;
			ptr += dp[!toFill][conhecidos+1] ;
 
			if(ptr >= MOD ) ptr -= MOD ;
 
		}
 
	}
 
	printf("%lld\n" , ans ) ;
 
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 1 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 #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
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 #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 4 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 #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 512 KB Output is correct
2 Correct 81 ms 504 KB Output is correct
3 Correct 86 ms 632 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 632 KB Output is correct
2 Correct 321 ms 632 KB Output is correct
3 Correct 322 ms 640 KB Output is correct