oj.uz

Submission #404287

# Submission time Handle Problem Language Result Execution time Memory
404287 2021-05-14T05:41:22 Z Andyvanh1 Studentsko (COCI14_studentsko) C++14
100 / 100
 44 ms 588 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <fstream>
#include <math.h>
#include <iomanip>


using namespace std;

#define vt vector
#define INF 0x3f3f3f3f
#define pb push_back
#define FORR1(n) for(int i = 0; i < n; i++)
#define FORR2(i,n) for(int i = 0; i < n; i++)
#define all(u) u.begin(),u.end()

typedef long long ll;
typedef vt<int> vi;
typedef pair<int,int> pii;

struct CTD{
    int size;
    vi par;
    vt<set<int>> tree;
    vi sub;
    void init(vt<set<int>> &adj){
        size = adj.size();
        par.resize(size);
        tree=adj;
        sub.resize(size);
        par[0] = -1;
        build(0,-1);
    }
    void build(int u, int p) {
        int n = dfs(u, p); // find the size of each subtree
        int centroid = find_centroid(u, p, n); // find the centroid
        par[centroid] = p;

        // for each tree resulting from the removal of the centroid
        set<int> ref = tree[centroid];
        for (auto v : ref) {
            tree[centroid].erase(v); // remove the edge to disconnect
            tree[v].erase(centroid); // the component from the tree
            build(v, centroid);
        }
    }



    int dfs(int u, int p) {
        sub[u] = 1;

        for (auto v : tree[u])
            if (v != p) sub[u] += dfs(v, u);

        return sub[u];
    }

    int find_centroid(int node, int p, int n){
        for(auto& e: tree[node]){
            if(e!=p&&sub[e]>n/2){
                return find_centroid(e,node,n);
            }
        }
        return node;
    }


};

struct fwtree{
    int size;
    vi arr;
    void init(int n){
        size = n;
        arr.resize(n+2);
        for(int i = 0; i < n+2; i++){
            arr[i] = 0;
        }
    }

    void update(int i, int x){
        for(; i <= size; i+=i&-i){
            arr[i]+=x;
        }
    }

    int get(int i){
        int ans = 0;
        for(; i > 0; i-=i&-i){
            ans+=arr[i];
        }
        return ans;
    }

    int get(int l, int r){
        return get(r)-get(l-1);
    }

};

struct point{
    long double x, y;

};

bool operator<(point p1, point p2){
   return p2.x>p1.x||(p2.x==p1.x&&p2.y>p1.y);
}

struct rect{
    int left, right, top, bottom;
};

pair<int,int> get(char c){
    if(c=='z'){
        return {9,4};
    }else if(c=='s'){
        return {7,4};
    }else if(c>'s'){
        c--;
    }

    int x = int(c-'a');
    return{x/3+2,x%3+1};

}

void solve(){
    int n, k;
    cin>>n>>k;
    vi arr(n);
    vi arr2(n);
    for(int i = 0; i < n; i++){
        cin>>arr[i];
        arr2[i] = arr[i];
    }
    sort(all(arr2));
    map<int,int> mp;
    for(int i = 0; i < n; i++){
        mp[arr2[i]] = i/k;
    }
    for(int i = 0; i < n; i++){
        arr[i] = mp[arr[i]];}

    int dp[n];

    dp[0] = 1;
    int ans = 1;
    for(int i = 1; i < n; i++){
        dp[i] = 1;
        for(int j = 0; j < i; j++){
            if(arr[j]<=arr[i]){
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        ans = max(ans,dp[i]);
    }
    cout<<n-ans<<'\n';

}

int main() {
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 588 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 556 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 460 KB Output is correct
2 Correct 37 ms 588 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 556 KB Output is correct
2 Correct 44 ms 588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 552 KB Output is correct
2 Correct 29 ms 588 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 460 KB Output is correct
2 Correct 42 ms 588 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 460 KB Output is correct
2 Correct 44 ms 588 KB Output is correct