#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
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;
stack<pair<int,int>> q;
vi arr(n);
for(int i = 0; i < n; i++){
cin>>arr[i];
}
int Max = 1;
for(int i = 1; i < n; i++){
q.push({arr[i]-1,Max});
Max = max(Max,arr[i]);
}
ll dp1[n+1][2];
for(int i = 1; i <= n; i++){
dp1[i][0] = 1;
}
ll ans = 0;
int x = 0;
while(!q.empty()){
auto& e = q.top();
q.pop();
ans+=(ll)e.first*dp1[e.second][x];
ans%=1000007;
x = 1-x;
for(int i = 1; i <= n; i++){
dp1[i][x] = (ll)i*dp1[i][1-x]+dp1[i+1][1-x];
dp1[i][1-x]%=1000007;
}
}
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 |
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 |
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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
233 ms |
636 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
79 ms |
656 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
273 ms |
620 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |