제출 #1215652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1215652		alimq	학생 (COCI14_studentsko)	C++20	100 / 100	9 ms	328 KiB

studentsko

#include <bits/stdc++.h>
using namespace std;

const int n0=5003;
int n,k,a[n0],p[n0],dp[n0];
array<int,2> b[n0];

int main() 
{
    cin >> n >> k;
    for(int i=0; i<n; i++) {
      cin >> a[i];
      b[i]={a[i],i};
    }
    sort(b,b+n);
    for(int i=0; i<n; i++) {
      p[b[i][1]]=i/k;
      // p - каким по величине является элемент, относительно других (0-й, 1-й, и т.д.)
      // делим на k, это будет номер блока
      // тогда нам нужно найти LIS (наибольшую возрастающую нестрого подпоследовательность)
      // ответ будет n-|LIS|
    }
    int ans=0;
    // dp[i] - |LIS| зак. на элемент i (p[j]=i)
    for(int j=0; j<n; j++) {
		int mx=0;
		for(int i=0; i<=p[j]; i++) {
			mx=max(mx,dp[i]);
		}
		dp[p[j]]=mx+1;
		ans=max(ans,dp[p[j]]);
	}
    cout << n-ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10