oj.uz

Submission #7982

# Submission time Handle Problem Language Result Execution time Memory
7982 2014-08-26T23:00:30 Z paulsohn 앱 (KOI13_app) C++
3.15 / 21
 1000 ms 1100 KB 
#include <stdio.h>
int N, M, c[100] = { 0 }, m[100] = { 0 }, deque[100] = { 0 }, front = 0, rear = 0, uber[100] = { 0 };
bool seg[100][100] = { 0 };
void push(int elm){
	deque[rear++] = elm; return;
}
int pop(){
	++front; return deque[front - 1];
}
int cost(int remmem){
	int first, used, unused, move=0;
	bool check[100] = { 0 };
	if (remmem <= 0) return 0;
	if (front == rear) return 10001;
	first = pop();
	for (int i = 0; i < N; ++i){
		if (seg[first][i]){
			check[i] = 1;
			seg[first][i] = 0;
			--uber[i];
			if (uber[i] == 0){
				push(i);
				++move;
			}
		}
	}
	unused = cost(remmem);
	used = c[first]+cost(remmem - m[first]);
	--front;
	rear -= move;
	for (int i = 1; i<N; ++i){
		if (check[i]){
			seg[first][i] = 1;
			++uber[i];
		}
	}
	if (used > unused) return unused;
	return used;
}
int main(){
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; ++i){
		scanf("%d", &m[i]);
	}
	for (int i = 0; i < N; ++i){
		scanf("%d", &c[i]);
		for (int j = 0; j < i; ++j){
			if ((c[i] <= c[j]) && (m[i] >= m[j])){
				seg[i][j] = 1;
				++uber[j];
			}
			else if ((c[i] >= c[j]) && (m[i] <= m[j])){
				seg[j][i] = 1;
				++uber[i];
			}
		}
	}
	for (int i = 0; i < N; ++i){
		if (uber[i] == 0) push(i);
	}
	printf("%d\n", cost(M));
	return 0;
}

Subtask #1
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1100 KB Output is correct
2 Correct 0 ms 1100 KB Output is correct
3 Correct 0 ms 1100 KB Output is correct
4 Correct 0 ms 1100 KB Output is correct
5 Correct 0 ms 1100 KB Output is correct

Subtask #3
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1096 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1100 KB Output is correct
2 Execution timed out 1000 ms 1096 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1096 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1096 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.1

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1096 KB Program timed out
2 Halted 0 ms 0 KB -