oj.uz

Submission #1070

# Submission time Handle Problem Language Result Execution time Memory
1070 2013-06-24T15:12:02 Z tncks0121 탐사 (KOI13_probe) C++
19 / 19
 84 ms 404 KB 
#include <stdio.h>
#include <algorithm>
FILE *in = stdin;
FILE *out = stdout;
int n, m;
int x[1605], y[1605], r[1605];
int st[45], end[45], maxsum[1605][45];
int px[45], py[45], max[45], cnt;
int path[45], flag;
int answer[45];
int a[45][45];
struct List{
int count, index;
bool operator()(List a,List b){
return a.count > b.count;
}
}list[85];
void dfs(int count){
int i, j;
if(count == cnt){flag=1; return;}
int maximum = 0;
for(j=0; j<n; j++) if(x[j] <= px [list[count].index] && py
[list[count].index] <= y[j]){if(r[j] - maxsum[j][count+1] > maximum)
maximum = r[j] - maxsum[j][count+1];}
int min = max[list[count].index];
for(j=0; j<n; j++) if(x[j] <= px [list[count].index] && py
[list[count].index] <= y[j]){if(min > r[j]) min = r[j];}
for(i=maximum; i<=min; i++){
for(j=0; j<n; j++) if(x[j] <= px [list[count].index] && py
[list[count].index] <= y[j]) r[j] -= i;
path[count] = i; dfs(count+1); if(flag) return;
path[count] = 0;
for(j=0; j<n; j++) if(x[j] <= px [list[count].index] && py
[list[count].index] <= y[j]) r[j] += i;
}
}
int main(){
int i,j;
fscanf(in,"%d %d",&m,&n);
for(i=1;i<=m;i++) for(j=1;j<=m;j++) a[i][j] = 1e9;
for(i=0; i<n; i++){
fscanf(in,"%d %d %d",&x[i],&y[i],&r[i]);
if(a[ x[i] ][ y[i] ] != 1e9){
if(a[ x[i] ][ y[i] ] !=
r[i]){fprintf(out,"NONE\n"); return 0;}
n--; i--;
}a
[ x[i] ][ y[i] ] = r[i];
}
int flagg;
for(;;){
flagg = 0;
for(i=0;i<n;i++) for(j=0;j<n;j++) if(x[i] == x[j] && y[i]
< y[j]) x[j] = y[i] + 1, r[j] = r[j] - r[i], flagg = 1;
for(i=0;i<n;i++) for(j=0;j<n;j++) if(y[i] == y[j] && x[i]
> x[j]) y[j] = x[i] - 1, r[j] = r[j] - r[i], flagg = 1;
for(i=0;i<n;i++){if(x[i] > y[i]){for(j=i;j<n-1;j++) x[j] =
x[j+1], y[j] = y[j+1], r[j] = r[j+1];n--;}}
if(flagg == 0) break;
}
for(i=0;i<n;i++) st[x[i]] = 1,end[y[i]] = 1;
int X, Y;
X = 1;
for(i=1; i<=m; i++){
if(st[i]) X = i;
if(end[i] || st[i+1]) Y = i, px[cnt] = X, py[cnt] = Y,
max[cnt++] = Y-X+1, X = Y+1;
}
for(i=0; i<n; i++)
for(j=0; j<cnt; j++)
if(x[i] <= px[j] && py[j] <= y[i]){
list[j].count ++;
if(max[j] > r[i]) max[j] = r[i];
}
for(i=0; i<cnt; i++) list[i].index = i;
std::sort(list, list+cnt, List());
for(i=0; i<n; i++)
for(j=cnt-1; j>=0; j--)
if(x[i] <= px[list[j].index] && py[list[j].index]
<= y[i]) maxsum[i][j] = maxsum[i][j+1] + max[list[j].index];
else maxsum[i][j] = maxsum[i][j+1];
dfs(0);
if(flag == 0){fprintf(out,"NONE\n");}
else{
for(i=0; i<cnt; i++) for(j = px[list[i].index]; j <=
py[list[i].index] && path[i]; j++) answer[j] = 1, path[i] --;
for(i=1; i<=m; i++) fprintf(out,(answer[i])?"#":"-");
}return 0;
}

Compilation message

probe.cpp: In function 'int main()':
probe.cpp:39:7: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 fscanf(in,"%d %d",&m,&n);
 ~~~~~~^~~~~~~~~~~~~~~~~~
probe.cpp:42:7: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 fscanf(in,"%d %d %d",&x[i],&y[i],&r[i]);
 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.47 / 2.47

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 1 ms 376 KB Output is correct
7 Correct 2 ms 348 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 256 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #3
1.33 / 1.33

# 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

Subtask #4
5.13 / 5.13

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

Subtask #5
3.61 / 3.61

# 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 3 ms 376 KB Output is correct

Subtask #6
4.37 / 4.37

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 82 ms 376 KB Output is correct
3 Correct 84 ms 364 KB Output is correct
4 Correct 3 ms 256 KB Output is correct