oj.uz

Submission #131108

# Submission time Handle Problem Language Result Execution time Memory
131108 2019-07-16T13:17:06 Z arthurconmy Calvinball championship (CEOI15_teams) C++14
100 / 100
 434 ms 832 KB 
/* Arthur Conmy / arthurconmy */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<int,int> pii;
#define REP(i, a, b) for (ll i = ll(a); i <= ll(b); i++)
#define REPb(j, d, c) for (ll j = ll(d); j >= ll(c); j--)
#define ff first
#define ss second
#define pb push_back
#define len(x) int((x).size())
#define endl "\n"

const ll MAXN=10001;
const ll p=1000007;

ll A[MAXN];

ll cur_pos[MAXN];
ll old_pos[MAXN];

ll cur_sz[MAXN];
ll old_sz[MAXN];

int main() // LL OR INT??
{
	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll n;
	cin>>n;

	if(n==1)
	{
		cout << 1 << endl;
		return 0;
	}

	ll thing_max=1;

	REP(i,1,n)
	{
		ll a;
		cin>>a;
		A[i]=a;
		thing_max=max(thing_max,a);
	}

	// sz[1][1]=ll(1);
	// pos[1][1]=ll(1);

	cur_sz[1]=1LL;
	cur_pos[1]=1LL;

	bool just_ones=1;
	ll cur_max=1;

	REP(i,2,n)
	{
		swap(cur_sz,old_sz);
		swap(cur_pos,old_pos);

		// sz[i][1]=1;

		cur_sz[1]=1;

		if(just_ones&&A[i]==1)
		{
			// pos[i][1]=0;
			cur_pos[1]=0LL;
		}

		else
		{
			just_ones=0;
			
			// pos[i][1]=1;
			cur_pos[1]=1LL;
		}

		// int j=1;
		// cout << i << " " << j << " " << pos[i][j] << endl;

		REP(j,2,i-1)
		{
			// sz[i][j]=sz[i-1][j-1]+j*sz[i-1][j];
			// sz[i][j]%=p;

			cur_sz[j]=old_sz[j-1]+j*old_sz[j];
			cur_sz[j]%=p;

			// pos[i][j]=pos[i-1][j-1]
			// 		 +j*pos[i-1][j]
			// 		 +ll(j==cur_max)*(A[i]-1);

			// pos[i][j]%=p;

			cur_pos[j]=old_pos[j-1]
					  +j*old_pos[j]
					  +ll(j==cur_max)*(A[i]-1LL);

			cur_pos[j]%=p;
		
			// cout << i << " " << j << " " << pos[i][j] << endl;
		}

		// cout << i << " " << i << " " << pos[i][i] << endl; 
		cur_pos[i]=0LL;
		cur_sz[i]=1LL;
	
		cur_max=max(cur_max,A[i]);
	}

	ll ans=0;

	REP(j,1,n)
	{
		ans+=cur_pos[j];
		ans%=p;
	}

	ans++;
	ans%=p;

	cout << ans << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 660 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 680 KB Output is correct
2 Correct 14 ms 728 KB Output is correct
3 Correct 14 ms 632 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 752 KB Output is correct
2 Correct 165 ms 752 KB Output is correct
3 Correct 174 ms 636 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 812 KB Output is correct
2 Correct 434 ms 800 KB Output is correct
3 Correct 431 ms 820 KB Output is correct