QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#69826 | #1389. Wycieczka górska [C] | mik | 10 ✓ | 312ms | 18780kb | C++14 | 891b | 2023-01-02 03:43:30 | 2023-01-02 03:43:32 |
Judging History
answer
#include <cstdio>
#include <utility>
#include <queue>
#define N 2000
int t[N][N];
std::queue <std::pair <int, int>> q;
int main ()
{
int n, m, k;
scanf ("%i%i%i", &n, &m, &k);
for (int i=0; i<n; i++) for (int j=0*scanf(" "); j<m; j++) t[i][j] = getchar()=='.'? N*N: -1;
t[0][0] = 0;
q.push({0, 0});
while (!q.empty())
{
auto [i, j] = q.front(); q.pop();
for (auto [x, y]: (int [][2]){{i+1, j}, {i, j+1}, {i-1, j}, {i, j-1}})
if (0<=x && x<n && 0<=y && y<m && t[x][y] > t[i][j]+1) t[x][y] = t[i][j]+1, q.push({x, y});
}
int g = (t[n-1][m-1] + (n-1+m-1))/2;
int d = (t[n-1][m-1] - (n-1+m-1))/2;
long long x = 1e18;
int y = 0;
while (k--)
{
int a, b;
scanf ("%i%i", &a, &b);
long long c = 1LL*a*g + 1LL*b*d;
if (c<x) x = c, y = 0;
if (c==x) y++;
}
printf ("%lli %i\n", x, y);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #3:
score: 1
Accepted
time: 3ms
memory: 2968kb
input:
5 7 1 ....... XXXXX.X ....... .XXXXXX ....... 2 1
output:
35 1
result:
ok single line: '35 1'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3204kb
input:
6 6 1 .X.... ...X.. ..X..X .X..X. X..X.. ...... 1 2
output:
19 1
result:
ok single line: '19 1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 2968kb
input:
6 6 1 ....X. ...... .....X ...X.. .XX.X. .XX... 3 2
output:
30 1
result:
ok single line: '30 1'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3072kb
input:
7 5 1 ..... ..... ..... ..... ..... ..... ..... 5 5
output:
50 1
result:
ok single line: '50 1'
Test #7:
score: 0
Accepted
time: 2ms
memory: 2956kb
input:
2 2 1 .X .. 4 3
output:
8 1
result:
ok single line: '8 1'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3188kb
input:
2 2 1 .. X. 1 5
output:
2 1
result:
ok single line: '2 1'
Test #9:
score: 0
Accepted
time: 2ms
memory: 2956kb
input:
2 2 1 .. .. 3 2
output:
6 1
result:
ok single line: '6 1'
Test #10:
score: 0
Accepted
time: 2ms
memory: 2932kb
input:
6 6 1 ...... .X.XX. .X.... .XXX.X .X...X ...X.. 4 5
output:
40 1
result:
ok single line: '40 1'
Subtask #2:
score: 1
Accepted
Test #11:
score: 1
Accepted
time: 0ms
memory: 3156kb
input:
60 60 10 ...X.X.X.X.X.X...X.X..X...X..X.X..X.X.....X......X...X...... XX.X.X.X.X.X.X.XXX.X..X......X.X..X.XXX.X.X.X.X.XX.X.X.XX.XX ...X.X.X...X.X.X.X.XX.XX.XX..X.X.XX.X...X.X.X.X....X....X.X. X.XX...X.X.X.X...X.X..X...X..X.X..X.XX.XX.X.X.XX.X...X..X... ...X.X...X...X.XXX.XX.XXX.XX.X....X.X...X.X.X.X...
output:
4694 1
result:
ok single line: '4694 1'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3080kb
input:
30 60 10 .X.....X.....X.....X.....X.....X.....X.....X.....X.....X.... ...X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X.. ..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X .X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X. X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X....
output:
62276 5
result:
ok single line: '62276 5'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3288kb
input:
60 30 10 .X.X.X.X.X.X.X...X.X.X..X.X.X. .X.X.X.X.X...X...X.X.X..X.X.X. .X.X...X.X.X.XX.XX.X.XX.X.X.X. .X.X.X.X.X.X.X...X.X.X..X.X.X. .X.X.X.X.X.X.XX.XX.X.X.XX.X.X. .X.X.X.X.X.X.X...X.X.X..X.X.X. .X.X.X.X.X.X.X...X.X.X......X. .....X...X.X.X.XXX.X.X..X.X.X. .X.X.X.X.X.X.X...X.X.XX.X.X.X. .X.X.X.X.X.X...
output:
11671 2
result:
ok single line: '11671 2'
Subtask #3:
score: 1
Accepted
Test #14:
score: 1
Accepted
time: 61ms
memory: 18532kb
input:
2000 2000 1 .X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.......
output:
221084180 1
result:
ok single line: '221084180 1'
Test #15:
score: 0
Accepted
time: 53ms
memory: 18568kb
input:
2000 1000 1 ..X..X.X...X....X..X.X.X.X..X..X..X.X.X.X..X.X.X..X..X.X.X..X..X..X.X..X.X..X.X..X..X..X.X..X.X.X.X.X..X.X.X.X..X..X.X.X.X....X......X..X....X.X.X..X.X..X.X.X...X.X..X..X.X..........X..X.....X.X.................X.X...X..X.X.X.X.X....X.X.X.X.X...X.X.X...X.X.X..X.X..X..X.X.X.X.X..X..X.X.X....
output:
36536613 1
result:
ok single line: '36536613 1'
Test #16:
score: 0
Accepted
time: 35ms
memory: 10968kb
input:
1000 2000 1 ..X....X.X......X.X.X..X..X..X.X.X.X.X...X.X.X.X..X.X.X..X.X..X.X..X..X..X..X.X.X.X........X.X..X..X.X..X.X.X..X..X..X...X.X..X.X..X.X..X.X..X...X..X.X..X.X..X.X.X.X...X.X..X.X.X..X.X..X.X.X.X.X.X..X..X.X..X.X...X.X.X..X..X...X.X..X..X..X..X.X..X..X.X.X.X.X..X.X..X.X.X.X.X..X.X.X.X.X...X...
output:
11669348 1
result:
ok single line: '11669348 1'
Subtask #4:
score: 1
Accepted
Test #17:
score: 1
Accepted
time: 2ms
memory: 3920kb
input:
200 200 1000 ..........................X..X.X.X.X........X..X.X..X..X..X.X.X.X.X.X.X.X.X...X.X.X.X..X.X.X.X..X..............X....X.X..X..X.X.X.X...X.X...X.X..X..X.X.X.X.X.X.X..X..X.X.X..X.X..X.X................... XXXXXXXXXXXXXXXXXXXXXXXXX.X..X.X.X.X.X.X..X.X.XX....X..X..X.X.X.X.......X.X...X.X.X.X....
output:
122831071550 1
result:
ok single line: '122831071550 1'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
200 200 1000 ..X.X.X.X.X.X.X.X..X.X.X.X.X..X..X..X.X..........X.X..X.X..X.X.X.X.X.X.X..X..X..X.X.X.X.................X.X.X.X..X.X.X......X.X.X.....X.X.X.X..X..X.X..X.X....X.X.X..X.X.X.X............................ .XX.X.X.X.X.X.X.XX.X.X.X.X.X..X..X..X.XX.XXXXXXXXX.X..X.X.XX.X.X.X.X.X.X..X..X..X.X.X....
output:
96930545678 1
result:
ok single line: '96930545678 1'
Test #19:
score: 0
Accepted
time: 4ms
memory: 3908kb
input:
200 200 1000 ..X.X.....X......X..X....X.X.X..X.X......X..........X...X..X.X.X.X....X....X.X.....X..................X.X.X..X.X.X.X.X..X.X.X..X.X.X..X.X.X.X.X.X.X.X...X...X..X..X..X.X..X.X.X.X.X.X.X..X..X....X.X.... ......XXX...XXXX......XX.............X.X...X.X..X.X...X............X....X......X.X.X.X...
output:
695240981688 2
result:
ok single line: '695240981688 2'
Subtask #5:
score: 1
Accepted
Test #20:
score: 1
Accepted
time: 199ms
memory: 2988kb
input:
20 20 1000000 ..X.X.X..X.X..X..... X.X.X.XX.X....X..XX. ..X.X.X..X.XX.X.XX.. X.X........X.....X.. ..X.X.X..X.XX.XXXX.X ..X.X.X..X.X..X..... .XX.X.XX.X.X.XXX.XX. ..X.X.X..X.X..X..... ....X.XX.X.XXXXXXX.X ..X.X.X..X.X........ XXXXXXXXXXXXXXXXXX.X .................... XXXXXXXXXXXXXXXXXX.X ................
output:
39413554590 499714
result:
ok single line: '39413554590 499714'
Test #21:
score: 0
Accepted
time: 196ms
memory: 3088kb
input:
10 20 1000000 .................X.. XXXXXXXXXXXXXXX.XX.. ....X............X.X ..X...XXXXXXXXX..... X.X.X..X.......X.X.. ..X.X.XX.XXX.X.X.X.X X.XXX....X.X.X...X.. ....X..X.X.X.X.X.X.X .X.XXX.X...X.X.X.X.. ....X..X.X.X.X.X.X.. 488213312 989554732 785631685 501560295 590156355 126090349 163789141 530506...
output:
963004 68
result:
ok single line: '963004 68'
Test #22:
score: 0
Accepted
time: 199ms
memory: 2992kb
input:
20 20 1000000 .XX..X.....X.......X ..XX....X...XX.....X X...X..........X..XX ...X..........X...X. .....XX.........X... X.....X........X.... ...X..X...X..X.X.... ....X.XX.....X.X...X X...X.XX...X.....XX. ..........X.......XX ...........XXXXX.... .....X.X..........X. ...X..........X..... .X...X.XX.......
output:
4050976586 199223
result:
ok single line: '4050976586 199223'
Subtask #6:
score: 1
Accepted
Test #23:
score: 1
Accepted
time: 16ms
memory: 6164kb
input:
500 500 100000 ......X.X.X...X...X.X.X.X..X..X.X.X.X.X..X.X.X..X.X..X.X.X.X.....X..X..X.X.X...X..X..X.X.X.X..X..X.X..X.X..X..X.X..X...X.X..X.X.X..X.X.X.X..X.X.X..X..X..X.X.X.X..X..X.X.X.X...X..X..X....X..X.X.X.X..X...X.X.X.X.X.X..X..X.X.X..X.X....X..X..X.X.X.X.X..X.X..X.X.X.X.X.X.X...X.X..X...X.X..X...
output:
6415369 16
result:
ok single line: '6415369 16'
Test #24:
score: 0
Accepted
time: 24ms
memory: 6164kb
input:
500 500 100000 .X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X....
output:
139018858 49735
result:
ok single line: '139018858 49735'
Test #25:
score: 0
Accepted
time: 18ms
memory: 5232kb
input:
500 100 100000 .....XX.......XX..XXX.......X..X...X......XXX....X.....X.XX..X.X.X.XX.....X..XX...X...X.XX.XX....... .....X....X.X....XXXX...X...X.....XX.X.X....XX...XX......X.XXX.XXX..XX.....XX...XX...X....X...X..XXX XX..X.....X.X..X...X.X.....XX....XXX.X..........XX.X........XX...X....X.X..X...XX.....
output:
243205 94
result:
ok single line: '243205 94'
Subtask #7:
score: 1
Accepted
Test #26:
score: 1
Accepted
time: 86ms
memory: 10872kb
input:
1000 1000 300000 ...........X...X...........X........X...X.X..X.X.X.X.X....X.......X.X....X....X......X.....X...X.X........X..........X.X..X............X...X.....X.X...X......X.X.X......X.X...X....X..X..X.X.X....X.X..X...X....X..........X..X.X.X.X.X.X..X.X.X.X.X....X....X..X.X.....X.X...X.X.X.X.X.X....
output:
128402819034 1
result:
ok single line: '128402819034 1'
Test #27:
score: 0
Accepted
time: 75ms
memory: 10848kb
input:
1000 1000 300000 .X..X.X.X.X.....X.X.X.X..X..X..X...X..X..............................X..X.X....................X..X.X.X.X.X.X.X.X..X.X.X......X..X............................................................X..X..X..X.X.X..X.X.X.X...X.X.X.X..X..X.X.X..X.X.X..X..X..X.X..X.X..X.X.X.X.X..X.X.X..X.X.X.X...
output:
5045390147614 2
result:
ok single line: '5045390147614 2'
Test #28:
score: 0
Accepted
time: 68ms
memory: 4588kb
input:
200 1000 300000 .X.X.X.X.X...................X..X.X..X.X..X.X.X..X..X...X.X....X...X.X.X.X....X.X...............X.X.X..X..X..X..X...X..X..X.X..X.X.....X..X.X..X..X........X.X.......X.X...X.X.X...X..X.....X.....X.X..X.X.X.X....X.X.X.X..X..X........................X..X.X..X.X.X.X.X.X..X.X.X..X.X.X.X.....
output:
6362046346613 3
result:
ok single line: '6362046346613 3'
Subtask #8:
score: 1
Accepted
Test #29:
score: 1
Accepted
time: 194ms
memory: 14904kb
input:
1500 1500 700000 ......X...XXX.X...XXX...X.XXX..X.X..........XX...X...X.X..X..X.XX...XXX....X...XX.X...X..XXX....X...X............XX..X.XXX...XX..X.X...X.XXX....XXXXX........X.X.X..X..X...X.XXX..XX.X..XXX.X.X..X...X.XXXX..XX..XXXXXXX.X...XX....X..XX....XX....X..X.......X..XX.X.X..X.X.....XX...X.X......
output:
1572674249854 349962
result:
ok single line: '1572674249854 349962'
Test #30:
score: 0
Accepted
time: 172ms
memory: 14668kb
input:
1500 1500 700000 .X.X.X.X..................X.....................................X........X...X....X.X.X.X.X.........X...X.......X..X.X.X..........X..X..X.X...X.......X...X..........X...X......X.X.....X..X...X....X........X.X..............X.........X.X....X...X.X.....X.X.X.X......X.X...X.....X.X.......
output:
55978349746505 7
result:
ok single line: '55978349746505 7'
Test #31:
score: 0
Accepted
time: 167ms
memory: 11868kb
input:
1500 500 700000 ...............................................................................................................................................................................................................................................................................................
output:
6849199609943 2
result:
ok single line: '6849199609943 2'
Test #32:
score: 0
Accepted
time: 162ms
memory: 14776kb
input:
1500 1500 700000 .X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X........
output:
1498000000000000 700000
result:
ok single line: '1498000000000000 700000'
Subtask #9:
score: 1
Accepted
Test #33:
score: 1
Accepted
time: 196ms
memory: 18580kb
input:
2000 2000 1000000 .X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.......
output:
2664002 1
result:
ok single line: '2664002 1'
Test #34:
score: 0
Accepted
time: 234ms
memory: 18600kb
input:
2000 2000 1000000 ...X.....X..XX...X..XX....X...X.X...X.....X....X...............XX.X....X.XXXX....X..XX...XX.X.XXXX.X...X.XX...XX.X.X..XX....X..XX....X....X..XX..X......X....X..X.....X..X...X........X.XX..X..X....X.X...X.....X.X.......XX.XXXX.X.X.X....X.XX.XX.X.X..X.XXX...X..X..X..X....X......X...X...
output:
653342 105
result:
ok single line: '653342 105'
Test #35:
score: 0
Accepted
time: 147ms
memory: 6948kb
input:
500 2000 1000000 ..X.X.X..X..X...X..X..X.......................X.......X...X..X.X....X.X.X.X.X.X...X..X..X..X.X....X....X....X..X........X.............................X...X.............X..........................X.X.X.X.....X..X................X..X.X.X.X..X.X..........X....X.X..X..X.X.X...X.X.X....X...
output:
7114460 499379
result:
ok single line: '7114460 499379'
Subtask #10:
score: 1
Accepted
Test #36:
score: 1
Accepted
time: 164ms
memory: 3964kb
input:
120 2000 1000000 .X.X.............................................................................................................................................................................................................................................................X.X.....X.X..X....X..X.X.X...
output:
1440196054163 8
result:
ok single line: '1440196054163 8'
Test #37:
score: 0
Accepted
time: 187ms
memory: 12032kb
input:
2000 120 1000000 .X...X.X....X.X.X.......X..X..X.X..X..X.X.X..X.X..X..X.X.X..X..X..X..X............X...X.X..X......X.X..X...X..X.X...X.X. .X.X.X.XX.X.X.X.XXXX.XXXX..X....XX.XX.X.X.XX.X.X.XXX.X.X.XX.XX.X..X..X..X.X.X..X....X......X.XX.XXX.XX.X.X.X..X.X...X.X. .X.X.X.X..X.............XX.XX.X.X..X..X.X...
output:
16257267210947 499769
result:
ok single line: '16257267210947 499769'
Test #38:
score: 0
Accepted
time: 87ms
memory: 18584kb
input:
2000 2000 500 .................................................................................................................................................................................................................................................................................................
output:
101396238158489 1
result:
ok single line: '101396238158489 1'
Test #39:
score: 0
Accepted
time: 279ms
memory: 18608kb
input:
2000 2000 1000000 .X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.......
output:
740987008504 1
result:
ok single line: '740987008504 1'
Test #40:
score: 0
Accepted
time: 276ms
memory: 18776kb
input:
2000 2000 1000000 ......................................X...............................................................................................................................................X...X.X..X.X..X.X.X..X.X..X.....X......X.X.X..X..X.X.X.X.X.X.X..X......................................
output:
83343407158700 18
result:
ok single line: '83343407158700 18'
Test #41:
score: 0
Accepted
time: 312ms
memory: 18628kb
input:
2000 2000 1000000 ....X...................X..X.X.......X....X.X...X...........XX..X.X..X.......XX..............X......X..............X.....X...X.X.XXX.X.X......X....X....X.....X.....X....X.........X..XX.X....XX.XX.X......X.................X.XX...............X....XXX.......X........X.....X.XX.X.........
output:
193471216 67
result:
ok single line: '193471216 67'
Test #42:
score: 0
Accepted
time: 275ms
memory: 18548kb
input:
2000 2000 1000000 .............................................................................................................................................................................................................................................................................................
output:
36021980 21
result:
ok single line: '36021980 21'
Test #43:
score: 0
Accepted
time: 282ms
memory: 18780kb
input:
2000 2000 1000000 .X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.....X.......
output:
2664002000000000 1000000
result:
ok single line: '2664002000000000 1000000'