#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define vt vector
#define INF INT_MAX
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vt<pair<int,int>> vpii;
vt<vi> adjlist;
vt<bool> visited;
void solve(){
int n, r;
cin>>n>>r;
adjlist.resize(n);
for(int i = 0; i < r; i++){
int u, v;
cin>>u>>v;
adjlist[u-1].pb(v-1);
adjlist[v-1].pb(u-1);
}
int sz = (1<<n);
bool bol1 = false;
for(int j = 1; j < sz; j++){
bool arr[n];
for(int i = 0; i < n; i++){
arr[i] = false;
}
int jj = j;
int idn = 0;
while(jj!=0){
if(jj%2==1){
arr[idn] = true;
}
jj/=2;
idn++;
}
vi a;
for(int i = 0; i < n; i++){
if(arr[i]){
a.pb(i);
}
}
if(a.size()<=3){
continue;
}
bool bol = true;
for(auto& e:a){
int ct = 0;
for(auto& ee: adjlist[e]){
if(arr[ee]){
ct++;
}
}
if(ct!=2){
bol = false;
break;
}
}
if(bol){
visited.resize(n);
for(int i = 0; i < n; i++){
visited[i] = false;
}
vi b;
stack<int> stk;
stk.push(a[0]);
visited[a[0]] = true;
while(!stk.empty()){
int node = stk.top();
stk.pop();
b.pb(node);
for(auto&e : adjlist[node]){
if(arr[e]&&!visited[e]){
stk.push(e);
visited[e] = true;
}
}
}
for(auto& e: b){
cout<<e+1<<" ";
}
bol1 = true;
break;
}
}
if(!bol1){
cout<<"no";
}
}
void solve2(){
int n;
cin>>n;
ll dp[n+1][n+1];
for(int i = 1; i <= n; i++){
dp[i][0] = 1;
}
for(int j = 1; j <= n; j++){
for(int i = 1; i <= n-j; i++){
dp[i][j] = i*dp[i][j-1]+dp[i+1][j-1];
dp[i][j]%=1000007;
}
}
vi arr(n);
for(int i = 0; i < n; i++){
cin>>arr[i];
}
ll ans = 0;
int Max = 1;
for(int i = 1; i < n; i++){
ans+=(arr[i]-1)*dp[Max][n-i-1];
ans%=1000007;
Max = max(Max,arr[i]);
}
cout<<ans+1;
}
int main() {
solve2();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2284 KB |
Output is correct |
2 |
Correct |
2 ms |
2284 KB |
Output is correct |
3 |
Correct |
2 ms |
2284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
7276 KB |
Output is correct |
2 |
Correct |
7 ms |
7276 KB |
Output is correct |
3 |
Correct |
9 ms |
7260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
126 ms |
65540 KB |
Execution killed with signal 9 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
151 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
108 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |