oj.uz

Submission #63647

# Submission time Handle Problem Language Result Execution time Memory
63647 2018-08-02T10:32:13 Z khohko Calvinball championship (CEOI15_teams) C++17
70 / 100
 650 ms 66560 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define ARRS ((ll)(2e6+500))
#define MAX ((ll)(1e6+100))
#define MOD ((ll)1e6+7)
#define mi(a,b) a=min((a),(b))

ll n,m,k,p,l,r,q;
ll a[ARRS];
int f[10050][1005][2];

ll slv(ll i,ll c,ll e=0){
	if(i==n)return 1;
	if(f[i][c][e])return f[i][c][e]-1;
	if(e){
		f[i][c][e]=c*slv(i+1,c,e)+slv(i+1,c+1,e);
		f[i][c][e]%=MOD;
		f[i][c][e]++;
		return f[i][c][e]-1;
	}
	else {
		ll pas=0;
		if(a[i]==c+1){
			pas+=c*slv(i+1,c,1);
			pas+=slv(i+1,c+1,0);
		}
		else {
			pas+=(a[i]-1)*slv(i+1,c,1);
			pas+=slv(i+1,c,0);
		}
		pas%=MOD;
		f[i][c][e]=pas+1;
		return pas;
	}
}

int main(){
	#ifdef KHOKHO
			freopen("in.in","r",stdin);
			freopen("out.out","w",stdout);
	#endif
	cin>>n;
	for(int i=0; i<n; i++)cin>>a[i];
	cout<<slv(0,0,0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 3 ms 560 KB Output is correct
6 Correct 2 ms 580 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7532 KB Output is correct
2 Correct 22 ms 7536 KB Output is correct
3 Correct 27 ms 7536 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 208 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 650 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -