제출 #1215650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1215650		alimq	Studentsko (COCI14_studentsko)	C++20	30 / 100	0 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;
    if(n>20) {
      return 0;
    }
    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: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10