oj.uz

답안 #255201

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255201 2020-07-31T14:14:19 Z Saboon Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 502 ms 257016 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e6 + 10;

int a[maxn], dp[maxn][32], r[maxn][32];


int extraprint(int k, int extra){
	if (extra == 0){
		printf("%d ", k);
		return 0;
	}
	int ret = extraprint(k-1, extra-1) + 1;
	extra -= ret;
	return ret + extraprint(k-1, extra);
}

int n;

int printer(int l, int k, int extra){
	if (a[l] == k){
		printf("%d ", k);
		return 0;
	}
	if (r[l][k-1] < n and r[r[l][k-1]][k-1] != -1){
		int ret = printer(l, k-1, extra);
		ret += printer(r[l][k-1], k-1, extra-ret);
		return ret;
	}
	int ret = printer(l, k-1, extra);
	ret += extraprint(k-1, extra-ret);
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	int k;
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	memset(r, -1, sizeof r);
	for (int i = n-1; i >= 0; i--){
		dp[i][a[i]] = 0;
		r[i][a[i]] = i+1;
		for (int l = a[i]+1; l <= 30; l++){
			if (r[i][l-1] < n and r[r[i][l-1]][l-1] != -1){
				r[i][l] = r[r[i][l-1]][l-1];
				dp[i][l] = dp[i][l-1] + dp[r[i][l-1]][l-1];
			}
			else{
				r[i][l] = r[i][l-1];
				dp[i][l] = dp[i][l-1] + 1;
			}
		}
	}
	assert(dp[0][30] <= k);
	printer(0, 30, k-dp[0][30]);
	printf("\n");
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 467 ms 256936 KB Output is correct
2 Correct 486 ms 256904 KB Output is correct
3 Correct 482 ms 256888 KB Output is correct
4 Correct 494 ms 256888 KB Output is correct
5 Correct 486 ms 257004 KB Output is correct
6 Correct 476 ms 256760 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 256880 KB Output is correct
2 Correct 499 ms 256700 KB Output is correct
3 Correct 495 ms 256632 KB Output is correct
4 Correct 492 ms 256912 KB Output is correct
5 Correct 479 ms 256900 KB Output is correct
6 Correct 481 ms 257016 KB Output is correct
7 Correct 490 ms 256888 KB Output is correct
8 Correct 475 ms 256888 KB Output is correct
9 Correct 408 ms 233464 KB Output is correct
10 Correct 278 ms 187556 KB Output is correct
11 Correct 345 ms 204792 KB Output is correct
12 Correct 195 ms 164856 KB Output is correct
13 Correct 194 ms 164856 KB Output is correct
14 Correct 198 ms 164856 KB Output is correct