oj.uz

Submission #96780

# Submission time Handle Problem Language Result Execution time Memory
96780 2019-02-12T01:25:28 Z Retro3014 Calvinball championship (CEOI15_teams) C++17
100 / 100
 677 ms 632 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;
#define DIV 1000007
#define MAX_N 10000
typedef long long ll;

int N;
ll DP1[MAX_N+1], DP2[MAX_N+1];
int arr[MAX_N+1];

int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		scanf("%d", &arr[i]);
	}
	int mx = 0;
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			DP2[j] =(DP1[j] * (ll)j + DP1[j -1]) % DIV;
		}
		for(int j=1; j<arr[i]; j++){
			DP2[max(mx, j)] = (DP2[max(mx, j)]+1)%DIV;
		}
		mx = max(mx, arr[i]);
		for(int j=0; j<=N; j++){
			DP1[j] = DP2[j]; DP2[j] = 0;
		}
	}
	ll ans = 0;
	for(int i=1; i<=N; i++){
		ans = (ans+DP1[i])%DIV;
	}
	printf("%lld", ans+1);
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 308 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 8 ms 372 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 376 KB Output is correct
2 Correct 86 ms 476 KB Output is correct
3 Correct 163 ms 504 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 632 KB Output is correct
2 Correct 338 ms 504 KB Output is correct
3 Correct 677 ms 632 KB Output is correct