QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69826#1389. Wycieczka górska [C]mik10 ✓312ms18780kbC++14891b2023-01-02 03:43:302023-01-02 03:43:32

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-02 03:43:32]
  • Judged
  • Verdict: 10
  • Time: 312ms
  • Memory: 18780kb
  • [2023-01-02 03:43:30]
  • Submitted

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'