oj.uz

Submission #499853

# Submission time Handle Problem Language Result Execution time Memory
499853 2021-12-29T19:39:53 Z Lobo Group Photo (JOI21_ho_t3) C++17
0 / 100
 0 ms 316 KB 
#include<bits/stdc++.h>
using namespace std;
 
/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/
 
const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
 
#define maxn 220
 
ii n, a[maxn], pos[maxn], bit[maxn], dp[maxn], mark[maxn];
 
void att(ii id, ii val) {
    for(ii i = id; i <= n; i+= i&-i) {
        bit[i]+= val;
    }
}
 
ii qr(ii id) {
    ii val = 0;
    for(ii i = id; i > 0; i-= i&-i) {
        val+= bit[i];
    }
    return val;
}
 
ii sol(ii i) {
    if(mark[i]) return dp[i];
    mark[i] = 1;
    ii ans = INFii;
    if(i == n) return dp[i] = 0;
 
    for(ii k = i+1; k <= n; k++) {
        ii ans1 = 0;
 
        for(ii j = 1; j <= n; j++) {
            bit[j] = 0;
        }
 
        for(ii j = 1; j <= i; j++) {
            att(pos[j],1);
        }
 

        for(ii j = i+1, x = k; j <= k; j++,x--) {
            ans1+= j-1-qr(pos[x]);
            att(pos[j],+1);
        }
 
        ans = min(ans, ans1+sol(k));
    }
 
    return dp[i] = ans;
}
 
void solve() {
    cin >> n;
 
    for(ii i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
 
    cout << sol(0) << endl;
 
    
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
 
    ii tt = 1;
    // cin >> tt;
    while(tt--) solve();
 
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 316 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 316 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 316 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 316 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 316 KB Output isn't correct
5 Halted 0 ms 0 KB -