QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #839715 | #1952. Window Shopping | crazyilian | AC ✓ | 226ms | 4912kb | C++23 | 4.7kb | 2025-01-02 06:50:54 | 2025-01-02 06:50:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct DpVal {
int totwind;
vector<int> winds;
vector<int> isud;
};
void relax(map<vector<int>, DpVal> &dp, vector<int> &comps, DpVal &val) {
vector<int> renum(val.winds.size(), -1);
int cc = 0;
for (int c : comps) {
if (c == -1 || renum[c] != -1)
continue;
renum[c] = cc++;
}
vector<int> ncomps(comps.size());
DpVal nval;
nval.totwind = val.totwind;
nval.winds.resize(cc, 0);
nval.isud.resize(cc, 0);
for (int i = 0; i < comps.size(); ++i) {
if (comps[i] == -1) {
ncomps[i] = -1;
continue;
}
int oldc = comps[i];
int newc = renum[oldc];
ncomps[i] = newc;
nval.winds[newc] = val.winds[oldc];
nval.isud[newc] = val.isud[oldc];
}
if (dp.find(ncomps) == dp.end() || dp[ncomps].totwind < nval.totwind)
dp[ncomps] = nval;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> field(n);
for (auto &el : field)
cin >> el;
if (n < m) {
vector<string> trans(m, string(n, '?'));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
trans[j][i] = field[i][j];
}
field = trans;
swap(n, m);
}
n++;
field.emplace_back(m, '#');
map<vector<int>, DpVal> dp;
dp[vector<int>(m, -1)] = {};
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
map<vector<int>, DpVal> ndp;
for (auto &[comps, val] : dp) {
if (field[i][j] == '#') {
// pillar
auto ncomps = comps;
auto nval = val;
ncomps[j] = -1;
if (comps[j] == -1 || count(comps.begin(), comps.end(), comps[j]) > 1)
relax(ndp, ncomps, nval);
else if (nval.isud[comps[j]] == 3)
ans = max(ans, nval.winds[comps[j]]);
continue;
}
if (field[i][j] == '.') {
// shop
auto ncomps = comps;
auto nval = val;
ncomps[j] = -1;
if (i > 0 && field[i - 1][j] == '.' && comps[j] != -1) {
nval.totwind++;
nval.winds[comps[j]]++;
}
if (j > 0 && field[i][j - 1] == '.' && comps[j - 1] != -1) {
nval.totwind++;
nval.winds[comps[j - 1]]++;
}
if (comps[j] == -1 || count(comps.begin(), comps.end(), comps[j]) > 1)
relax(ndp, ncomps, nval);
else if (nval.isud[comps[j]] == 3)
ans = max(ans, nval.winds[comps[j]]);
}
{
// walkable
auto ncomps = comps;
auto nval = val;
int c = nval.winds.size();
ncomps[j] = c;
nval.winds.push_back(0);
nval.isud.push_back(0);
if (comps[j] != -1) {
// merge up
nval.winds[c] += val.winds[comps[j]];
nval.isud[c] |= val.isud[comps[j]];
replace(ncomps.begin(), ncomps.end(), comps[j], c);
}
if (j > 0 && comps[j - 1] != -1 && ncomps[j - 1] != c) {
// merge left
nval.winds[c] += val.winds[comps[j - 1]];
nval.isud[c] |= val.isud[comps[j - 1]];
replace(ncomps.begin(), ncomps.end(), comps[j - 1], c);
}
if (field[i][j] == '.') {
// add windows
if (i > 0 && field[i - 1][j] == '.' && comps[j] == -1) {
nval.totwind++;
nval.winds[c]++;
}
if (j > 0 && field[i][j - 1] == '.' && comps[j - 1] == -1) {
nval.totwind++;
nval.winds[c]++;
}
} else if (field[i][j] == 'U') {
nval.isud[c] |= 1;
} else if (field[i][j] == 'D') {
nval.isud[c] |= 2;
}
relax(ndp, ncomps, nval);
}
}
swap(dp, ndp);
}
}
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
5 5 ..D#. .#... .#... .#... ..U#.
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
5 5 U...# ...#. ..... .#... #...D
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
4 5 ..... ..#.. .#U#. ..D..
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 4 .... .##. ..#. .#U# ...D
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
2 5 .U.D. ..#.#
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 10 #.....###. ..#.#.UD..
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
3 3 D.. ... ..U
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 3 #.. .U. ..D
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
5 4 .... .... ..U. .D.. ....
output:
16
result:
ok single line: '16'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 20 ##.............U.D.#
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
20 1 # . . D . . . . . . . . U . . . . . . .
output:
2
result:
ok single line: '2'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
9 9 U#....... .#.#####. .#.#...#. .#.#.#.#. .#.#.#.#. .#.#.#.#. .#.#.#.#. .#.#.#.#. ...#D#...
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 8ms
memory: 3996kb
input:
9 11 ........... .###.#####. .#...#..D#. U#...#...#. .######.##. .#.......#. .#.......#. .###.#####. ...........
output:
19
result:
ok single line: '19'
Test #14:
score: 0
Accepted
time: 15ms
memory: 4360kb
input:
10 9 ......... ......... .#######. .#D#U#.#. .#.#.#.#. .#.#..... .#.###### .#....... ..######. .........
output:
16
result:
ok single line: '16'
Test #15:
score: 0
Accepted
time: 203ms
memory: 4852kb
input:
9 11 ........... ........... ........... ........... .....D..... ....U...... ........... ........... ...........
output:
111
result:
ok single line: '111'
Test #16:
score: 0
Accepted
time: 226ms
memory: 4912kb
input:
9 11 ........... ........... ........... ........... ........... ........... ........... ........... U.........D
output:
112
result:
ok single line: '112'
Test #17:
score: 0
Accepted
time: 9ms
memory: 3752kb
input:
11 9 ..#..#..# ..#..#... #..#..#.. #.D#..#.. ..#..#..# ..#..U..# #.....#.. #..#..#.. ..#..#..# ..#..#..# ..#.....#
output:
41
result:
ok single line: '41'
Test #18:
score: 0
Accepted
time: 16ms
memory: 4484kb
input:
9 11 ........... .#.#####... ..#....#... .#..#...#.. .#.#U#..#.. .#.#D...#.. .#..####... .#......... .#.#....#..
output:
35
result:
ok single line: '35'
Test #19:
score: 0
Accepted
time: 3ms
memory: 4104kb
input:
11 9 ......... .#.#####. ..#.#..#. .#..#...# .#.#D#..# .#.#..... .#..##.#. ........# .#######. ......... .#######U
output:
15
result:
ok single line: '15'
Test #20:
score: 0
Accepted
time: 22ms
memory: 4008kb
input:
9 11 .#.#.#.#.#. ........... .#.#.#.#.#. ........... .#.#.U.#.#. ........... .#.D.#.#.#. ........... .#.#.#.#.#.
output:
46
result:
ok single line: '46'
Test #21:
score: 0
Accepted
time: 5ms
memory: 3776kb
input:
9 11 ...#U#...## .#.....#... ##.#.#.#.## .#.#.#.#... .#.#.###### ...#.#..D.. .#.#.#.#.## .#.....#... .#.#.###.##
output:
13
result:
ok single line: '13'
Test #22:
score: 0
Accepted
time: 15ms
memory: 4680kb
input:
11 9 ......... ......... #####U### ......... ####.#### ......... #####...# ......... #####D### ......... ##....###
output:
32
result:
ok single line: '32'
Test #23:
score: 0
Accepted
time: 17ms
memory: 4684kb
input:
9 11 .#..#...#.# .#..#...#.# .#......D.. .#..#...#.. .U..#...#.. .#..#.#.#.. .#..#.#.#.# .#..#.#.#.# .#..#.#.#.#
output:
36
result:
ok single line: '36'
Test #24:
score: 0
Accepted
time: 5ms
memory: 3868kb
input:
9 11 ........... .#.######.. .#.#.#..#.. .#.#.#..#.. .#.#.#.#..# .#.#.#.#.#D .#.#.#.#.#. .#.#.#...#. .#U#.......
output:
12
result:
ok single line: '12'
Test #25:
score: 0
Accepted
time: 5ms
memory: 3956kb
input:
9 11 ........... .#########. .#......... .#.######## D#....U#... .#######... .#......... .#.######## ...........
output:
8
result:
ok single line: '8'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
9 11 ########### ########### ########### ########### ########### ########### #######UD## ########### ###########
output:
0
result:
ok single line: '0'
Test #27:
score: 0
Accepted
time: 17ms
memory: 4588kb
input:
9 11 ##.D#..#..# .##..#U#... ...#.#....# #.......... .#....#..#. ....#...... ..###..#... ....###...# .##........
output:
44
result:
ok single line: '44'
Test #28:
score: 0
Accepted
time: 31ms
memory: 4584kb
input:
9 11 ##..#.....# .....#...#. ...###...D. #.......##. #..U#...... ..#....##.. ..#....###. ........#.. ....#...#..
output:
56
result:
ok single line: '56'
Test #29:
score: 0
Accepted
time: 23ms
memory: 4184kb
input:
9 11 .....#.#... .#......... ..#.##....# ..#..#D..## ....#.....# ....#.#.##. ...#.....#U ......#.... ##.#.#....#
output:
50
result:
ok single line: '50'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
5 19 ....#....#..#..#.#. #........#..#..#... ..#...#.#....U..... .......D..#.....#.. .#.....#.#......#..
output:
56
result:
ok single line: '56'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
5 19 ......#....#.....## .#...........#.#.## #......#...U..#.#.# ..........#.#...#.. ....#..#.D.........
output:
52
result:
ok single line: '52'
Test #32:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
5 19 ................... .....#........##... .#..#...##.....#... #.......#...#..#... ..#.#.U.#.....D#...
output:
60
result:
ok single line: '60'
Test #33:
score: 0
Accepted
time: 4ms
memory: 3688kb
input:
16 6 ...... ..U#.. #..... .#.#.. ....#. #..... .....# .#.#.. ...... ...... #....# .....# .#D.#. ....#. ...... #.#...
output:
61
result:
ok single line: '61'
Test #34:
score: 0
Accepted
time: 4ms
memory: 3832kb
input:
16 6 ....#. #..... ##.#.. ...... ...... .....# ....D. ..#### ....## ..#... #...## ....U. ..#... ....#. ...... ....#.
output:
61
result:
ok single line: '61'
Test #35:
score: 0
Accepted
time: 3ms
memory: 3592kb
input:
16 6 .....# #.#... ...... .D.... #..#.. .#.... ...##. .....U .##... ...... .#..#. #..#.# .....# .....# ...... #..#..
output:
58
result:
ok single line: '58'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
5 5 ...U. ....D ..... ..... ...##
output:
20
result:
ok single line: '20'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
4 4 U.D. .... #.## #.##
output:
5
result:
ok single line: '5'