#include<bits/stdc++.h>
using namespace std;
int n, v[200002], sortt[200002];
map<int, int> mp;
int dp[1002][1002];
int cnt[1002][1002];
const int mod = 1000000007;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> v[i];
sortt[i] = v[i];
}
sort(sortt + 1, sortt + n + 1);
int valdis = 0;
for(int i = 1; i <= n; ++i)
if(i == 1 || sortt[i] > sortt[i-1])
mp[sortt[i]] = ++valdis;
for(int i = 1; i <= n; ++i)
v[i] = mp[v[i]];
dp[v[1]][v[1]] = cnt[v[1]][v[1]] = 1;
int put = 1;
bool ok = 1;
for(int i = 2; i <= n; ++i)
{
for(int j = 1; j <= valdis; ++j)
for(int k = valdis; k >= j; --k)
{
if(!dp[j][k])
continue;
/*
if(j <= v[i] && v[i] <= k)
{
cnt[j][k] = (cnt[j][k] + cnt[j][k]);
if(cnt[j][k] >= mod)
cnt[j][k] -= mod;
}
else
{
*/
if(v[i] < j)
{
if(dp[j][k] + 1 > dp[v[i]][k])
{
dp[v[i]][k] = dp[j][k] + 1;
cnt[v[i]][k] = cnt[j][k];
}
else if(dp[j][k] + 1 == dp[v[i]][k])
{
cnt[v[i]][k] = (cnt[v[i]][k] + cnt[j][k]);
if(cnt[v[i]][k] >= mod)
cnt[v[i]][k] -= mod;
}
}
if(v[i] > k)
{
if(dp[j][k] + 1 > dp[j][v[i]])
{
dp[j][v[i]] = dp[j][k] + 1;
cnt[j][v[i]] = cnt[j][k];
}
else if(dp[j][k] + 1 == dp[j][v[i]])
{
cnt[j][v[i]] = (cnt[j][v[i]] + cnt[j][k]);
if(cnt[j][v[i]] >= mod)
cnt[j][v[i]] -= mod;
}
}
// }
}
if(v[i] != v[i-1])
ok = 0;
if(ok)
{
put = put + put;
if(put >= mod)
put -= mod;
dp[v[i]][v[i]] = 1;
cnt[v[i]][v[i]] = cnt[v[i]][v[i]] + cnt[v[i]][v[i]];
if(cnt[v[i]][v[i]] >= mod)
cnt[v[i]][v[i]] -= mod;
cnt[v[i]][v[i]] += put;
if(cnt[v[i]][v[i]] >= mod)
cnt[v[i]][v[i]] -= mod;
}
else
{
dp[v[i]][v[i]] = 1;
cnt[v[i]][v[i]] += put;
if(cnt[v[i]][v[i]] >= mod)
cnt[v[i]][v[i]] -= mod;
}
// cout << dp[1][2] << " " << cnt[1][2] << '\n';
// cout << dp[1][3] << " " << cnt[1][3] << '\n';
for(int j = 1; j <= valdis; ++j)
{
int maxv = 0;
for(int k = j; k <= valdis; ++k)
if(dp[j][k] < maxv)
dp[j][k] = cnt[j][k] = 0;
else
maxv = dp[j][k];
}
}
int bst = 0;
int nr = 0;
for(int i = 1; i <= valdis; ++i)
for(int j = i; j <= valdis; ++j)
if(dp[i][j] > bst)
{
bst = dp[i][j];
nr = cnt[i][j];
}
else if(dp[i][j] == bst)
{
nr = nr + cnt[i][j];
if(nr >= mod)
nr -= mod;
}
cout << bst << " " << nr << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
504 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Execution timed out |
1098 ms |
8248 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1097 ms |
8180 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1100 ms |
8184 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1095 ms |
8204 KB |
Time limit exceeded |
| 11 |
Runtime error |
243 ms |
20600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
243 ms |
17912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
207 ms |
16888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
123 ms |
15736 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
175 ms |
19576 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
201 ms |
22520 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
127 ms |
19704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
128 ms |
19492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
129 ms |
19636 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
127 ms |
19580 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
