Submission #734439

#	Time	Username	Problem	Language	Result	Execution time	Memory
734439		lovrot	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	109 ms	133548 KiB

prison

#include <cstdio> 
#include <algorithm> 
#include <cstring>

#define X first
#define Y second
#define pb push_back

using namespace std; 

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

const int LOG = 12; 
const int OFF = 1 << LOG; 
const int INF = 2e9; 
const int N = 4010; 

int n, d, t, C[OFF], E[OFF]; 
int T[2 * OFF], P[2 * OFF]; 

void add(int x, int val) {
	T[x] += val; 
	P[x] += val;
}

void propagate(int x) {
	if(x >= OFF) return;
	add(2 * x, P[x]);
	add(2 * x + 1, P[x]); 
	P[x] = 0;
}

void climb(int x, int val) {
	x += OFF;
	T[x] = val; 
	x /= 2;
	for(x; x; x /= 2)
		T[x] = min(T[2 * x], T[2 * x + 1]); 
}

int update(int l, int r, int val, int x = 1, int lo = 0, int hi = OFF) {
	if(r <= hi || lo <= l) return INF; 
	if(l <= lo && hi <= r) {
		add(x, val); 
		return T[x]; 
	}
	propagate(x);
	int mi = (lo + hi) / 2;
	T[x] = min(update(l, r, val, 2 * x, lo, mi), update(l, r, val, mi, hi)); 
	return T[x]; 	
}

int query(int val, int x = 1, int lo = 0, int hi = OFF) {
	if(lo + 1 == hi) return lo; 
	if(T[x] > val) return -1;
	int mi = (lo + hi) / 2;
	if(T[2 * x + 1] <= val) return query(val, 2 * x + 1, mi, hi);
	return query(val, 2 * x, lo, mi);
} 

int DP[OFF][OFF];

int dyn(int i, int w) {
	if(i >= n) return 0;
	if(DP[i][w] != -1) return DP[i][w]; 
	DP[i][w] = 0;
	for(int j = i; j < n; j++) DP[i][w] += E[j] >= i; 
	if(w) {
		int cnt = 0;
		for(int j = i; j < n; j++) {
			cnt += E[j] >= i; 
			DP[i][w] = min(DP[i][w], cnt + dyn(j + 1, w - 1)); 
		} 
	}
	return DP[i][w]; 
}

int main() {
	for(int i = 0; i < 2 * OFF; i++) T[i] = INF;
	memset(DP, -1, sizeof(DP)); 
	
	scanf("%d%d%d", &n, &d, &t);
	d = min(d, n);
	for(int i = 0; i < n; i++) {
		scanf("%d", C + i);
		climb(i, C[i]), update(0, i, 1); 
		E[i] = query(t); 
		//printf("// %d %d\n", i, E[i]);
	} 
	printf("%d\n", dyn(0, d)); 
	return 0;
}

Compilation message (stderr)

prison.cpp: In function 'void climb(int, int)':
prison.cpp:38:6: warning: statement has no effect [-Wunused-value]
   38 |  for(x; x; x /= 2)
      |      ^
prison.cpp: In function 'int main()':
prison.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d%d", &n, &d, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
prison.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d", C + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20