oj.uz

Submission #20216

# Submission time Handle Problem Language Result Execution time Memory
20216 2016-04-13T06:51:16 Z forever426 탐사 (KOI13_probe) C
14.63 / 19
 2000 ms 376 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int K, N;
typedef struct st
{
	int s;
	int e;
	int n;
}SEARCH;
SEARCH S[1000+10];

int Map[40+5];
int End[40+5];
int Check_sum[41][41];
int Check_line[41][2];

int CMP(const void * a, const void * b)
{
	return ((SEARCH*)a)->e - ((SEARCH*)b)->e; 
}
int DFS(int n, int c)
{
	int i, m;
	if(n>K) return 1;

	Map[n] = c;

	for(i=n; i>0; i--) Check_sum[i][n] = Check_sum[i][n-1] + c;

	if(Check_line[n][0]<Check_sum[Check_line[n][1]][n]) return 0;

	m = End[n];	
	while(n==S[m].e)
	{	
		if(Check_sum[S[m].s][n] != S[m].n) return 0;
		m--;
	}

	if(DFS(n+1, 1)) return 1;
	if(DFS(n+1, 0)) return 1;
	return 0;
}


int main(void)
{
	int i, j;
	scanf("%d%d", &K, &N);

	for(i=1; i<=N; i++) scanf("%d%d%d", &S[i].s, &S[i].e, &S[i].n);

	qsort(S+1, N, sizeof(S[0]), CMP);

	for(j=0; j<=K; j++) Check_line[j][0] = 50;
	
	for(i=1; i<=N; i++) {
		for(j=S[i].s; j<=S[i].e; j++) {
			if(Check_line[j][0] > S[i].n) {
				Check_line[j][0] = S[i].n;
				Check_line[j][1] = S[i].s;
			}
		}
	}

	for(i=1; i<=N; i++) End[S[i].e] = i;

	if(DFS(1,1) || DFS(1,0)) {
		for(i=1; i<=K; i++)	{
			if(Map[i]) printf("#");
			else printf("-");
		}
	}
	else printf("NONE\n");
}

Compilation message

probe.c: In function 'main':
probe.c:50:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &K, &N);
  ^~~~~~~~~~~~~~~~~~~~~
probe.c:52:22: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d%d%d", &S[i].s, &S[i].e, &S[i].n);
                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.47 / 2.47

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct

Subtask #2
2.09 / 2.09

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #3
1.33 / 1.33

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 20 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct

Subtask #4
5.13 / 5.13

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 12 ms 256 KB Output is correct

Subtask #5
3.61 / 3.61

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 58 ms 376 KB Output is correct

Subtask #6
0 / 4.37

# Verdict Execution time Memory Grader output
1 Correct 32 ms 252 KB Output is correct
2 Correct 1262 ms 348 KB Output is correct
3 Execution timed out 2081 ms 256 KB Time limit exceeded
4 Halted 0 ms 0 KB -