#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("input.000","r",stdin);
// freopen("output.000","w",stdout);
// srand((unsigned)time(NULL));
// rand()
int n,i,j,k,a[5005],dp[5005],b[5005],m,cost,pos[5005];
ordered_set s;
cin>>n;
for (i=1;i<n+1;i++) cin>>a[i];
dp[n]=dp[n+1]=0;
for (i=n-1;i>0;i--)
{
dp[i]=1e12;
m=0;
for (j=1;j<n+1;j++) if (a[j]>=i)
{
m++;b[m]=a[j];
}
for (j=1;j<m+1;j++) pos[b[j]]=j;
for (j=i+1;j<=n+1;j++)
{
while (s.begin()!=s.end()) s.erase(s.begin());
for (k=j;k<n+1;k++) s.insert(pos[k]);
cost=0;
for (k=i;k<j;k++)
{
cost += s.order_of_key(pos[k]);
s.insert(pos[k]);
}
// cout<<i<<" "<<j<<" "<<cost<<"\n";
dp[i]=min(dp[i], cost + dp[j]);
}
}
cout<<dp[1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
468 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
468 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
596 KB |
Output is correct |
| 17 |
Correct |
1 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
468 KB |
Output is correct |
| 20 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
468 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
596 KB |
Output is correct |
| 17 |
Correct |
1 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
468 KB |
Output is correct |
| 20 |
Correct |
1 ms |
468 KB |
Output is correct |
| 21 |
Correct |
409 ms |
584 KB |
Output is correct |
| 22 |
Correct |
440 ms |
588 KB |
Output is correct |
| 23 |
Correct |
408 ms |
468 KB |
Output is correct |
| 24 |
Correct |
416 ms |
584 KB |
Output is correct |
| 25 |
Correct |
415 ms |
468 KB |
Output is correct |
| 26 |
Correct |
420 ms |
460 KB |
Output is correct |
| 27 |
Correct |
423 ms |
340 KB |
Output is correct |
| 28 |
Correct |
414 ms |
468 KB |
Output is correct |
| 29 |
Correct |
428 ms |
456 KB |
Output is correct |
| 30 |
Correct |
419 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
468 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
596 KB |
Output is correct |
| 17 |
Correct |
1 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
468 KB |
Output is correct |
| 20 |
Correct |
1 ms |
468 KB |
Output is correct |
| 21 |
Correct |
409 ms |
584 KB |
Output is correct |
| 22 |
Correct |
440 ms |
588 KB |
Output is correct |
| 23 |
Correct |
408 ms |
468 KB |
Output is correct |
| 24 |
Correct |
416 ms |
584 KB |
Output is correct |
| 25 |
Correct |
415 ms |
468 KB |
Output is correct |
| 26 |
Correct |
420 ms |
460 KB |
Output is correct |
| 27 |
Correct |
423 ms |
340 KB |
Output is correct |
| 28 |
Correct |
414 ms |
468 KB |
Output is correct |
| 29 |
Correct |
428 ms |
456 KB |
Output is correct |
| 30 |
Correct |
419 ms |
468 KB |
Output is correct |
| 31 |
Execution timed out |
5006 ms |
592 KB |
Time limit exceeded |
| 32 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
468 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
596 KB |
Output is correct |
| 17 |
Correct |
1 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
468 KB |
Output is correct |
| 20 |
Correct |
1 ms |
468 KB |
Output is correct |
| 21 |
Correct |
409 ms |
584 KB |
Output is correct |
| 22 |
Correct |
440 ms |
588 KB |
Output is correct |
| 23 |
Correct |
408 ms |
468 KB |
Output is correct |
| 24 |
Correct |
416 ms |
584 KB |
Output is correct |
| 25 |
Correct |
415 ms |
468 KB |
Output is correct |
| 26 |
Correct |
420 ms |
460 KB |
Output is correct |
| 27 |
Correct |
423 ms |
340 KB |
Output is correct |
| 28 |
Correct |
414 ms |
468 KB |
Output is correct |
| 29 |
Correct |
428 ms |
456 KB |
Output is correct |
| 30 |
Correct |
419 ms |
468 KB |
Output is correct |
| 31 |
Execution timed out |
5006 ms |
592 KB |
Time limit exceeded |
| 32 |
Halted |
0 ms |
0 KB |
- |
