oj.uz

Submission #734676

# Submission time Handle Problem Language Result Execution time Memory
734676 2023-05-02T19:30:41 Z lovrot The short shank; Redemption (BOI21_prison) C++17
15 / 100
 2000 ms 133900 KB 
#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;
}

int desc(int ind, int val, int x = 1, int lo = 0, int hi = OFF) {
	if(ind + 1 <= lo || hi <= ind) return T[x]; 
	if(lo + 1 == hi) {
		T[x] = val; 
		P[x] = 0;
		return T[x]; 
	}
	propagate(x); 
	int mi = (lo + hi) / 2;
	T[x] = min(desc(ind, val, 2 * x, lo, mi), desc(ind, val, 2 * x + 1, mi, hi));
	return T[x];   
}

int update(int l, int r, int val, int x = 1, int lo = 0, int hi = OFF) {
	if(r <= lo || hi <= l) return T[x]; 
	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, 2 * x + 1, 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;
	propagate(x);
	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);
		desc(i, C[i]), update(0, i, 1); 
		E[i] = query(t); 
	} 
	printf("%d\n", dyn(0, d)); 
	return 0;
}

Compilation message

prison.cpp: In function 'int main()':
prison.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d%d%d", &n, &d, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
prison.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%d", C + i);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 65940 KB Output is correct
2 Correct 33 ms 66004 KB Output is correct
3 Correct 40 ms 66004 KB Output is correct
4 Correct 66 ms 65992 KB Output is correct
5 Correct 119 ms 65976 KB Output is correct
6 Correct 28 ms 65968 KB Output is correct
7 Correct 62 ms 65888 KB Output is correct
8 Correct 40 ms 65980 KB Output is correct
9 Correct 45 ms 65940 KB Output is correct
10 Correct 90 ms 65980 KB Output is correct
11 Correct 109 ms 65988 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 65984 KB Output is correct
2 Runtime error 87 ms 133900 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 65940 KB Output is correct
2 Correct 33 ms 66004 KB Output is correct
3 Correct 40 ms 66004 KB Output is correct
4 Correct 66 ms 65992 KB Output is correct
5 Correct 119 ms 65976 KB Output is correct
6 Correct 28 ms 65968 KB Output is correct
7 Correct 62 ms 65888 KB Output is correct
8 Correct 40 ms 65980 KB Output is correct
9 Correct 45 ms 65940 KB Output is correct
10 Correct 90 ms 65980 KB Output is correct
11 Correct 109 ms 65988 KB Output is correct
12 Correct 26 ms 65956 KB Output is correct
13 Correct 36 ms 65980 KB Output is correct
14 Correct 38 ms 65896 KB Output is correct
15 Correct 74 ms 65988 KB Output is correct
16 Correct 112 ms 65988 KB Output is correct
17 Correct 28 ms 66004 KB Output is correct
18 Correct 64 ms 65992 KB Output is correct
19 Correct 37 ms 65896 KB Output is correct
20 Correct 49 ms 65968 KB Output is correct
21 Correct 71 ms 65980 KB Output is correct
22 Correct 99 ms 65976 KB Output is correct
23 Execution timed out 2066 ms 66004 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65952 KB Output is correct
2 Runtime error 82 ms 133812 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 65940 KB Output is correct
2 Correct 33 ms 66004 KB Output is correct
3 Correct 40 ms 66004 KB Output is correct
4 Correct 66 ms 65992 KB Output is correct
5 Correct 119 ms 65976 KB Output is correct
6 Correct 28 ms 65968 KB Output is correct
7 Correct 62 ms 65888 KB Output is correct
8 Correct 40 ms 65980 KB Output is correct
9 Correct 45 ms 65940 KB Output is correct
10 Correct 90 ms 65980 KB Output is correct
11 Correct 109 ms 65988 KB Output is correct
12 Correct 26 ms 65956 KB Output is correct
13 Correct 36 ms 65980 KB Output is correct
14 Correct 38 ms 65896 KB Output is correct
15 Correct 74 ms 65988 KB Output is correct
16 Correct 112 ms 65988 KB Output is correct
17 Correct 28 ms 66004 KB Output is correct
18 Correct 64 ms 65992 KB Output is correct
19 Correct 37 ms 65896 KB Output is correct
20 Correct 49 ms 65968 KB Output is correct
21 Correct 71 ms 65980 KB Output is correct
22 Correct 99 ms 65976 KB Output is correct
23 Execution timed out 2066 ms 66004 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 65940 KB Output is correct
2 Correct 33 ms 66004 KB Output is correct
3 Correct 40 ms 66004 KB Output is correct
4 Correct 66 ms 65992 KB Output is correct
5 Correct 119 ms 65976 KB Output is correct
6 Correct 28 ms 65968 KB Output is correct
7 Correct 62 ms 65888 KB Output is correct
8 Correct 40 ms 65980 KB Output is correct
9 Correct 45 ms 65940 KB Output is correct
10 Correct 90 ms 65980 KB Output is correct
11 Correct 109 ms 65988 KB Output is correct
12 Correct 24 ms 65984 KB Output is correct
13 Runtime error 87 ms 133900 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -