Submission #404287

#TimeUsernameProblemLanguageResultExecution timeMemory
404287Andyvanh1Studentsko (COCI14_studentsko)C++14
100 / 100
44 ms588 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...