QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133950#6259. Gluttonous GoopKhNURE_KIVI#AC ✓1801ms370284kbC++233.9kb2023-08-02 18:03:172023-08-02 18:03:18

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 18:03:18]
  • 评测
  • 测评结果:AC
  • 用时:1801ms
  • 内存:370284kb
  • [2023-08-02 18:03:17]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int r, c, k;
    cin >> r >> c >> k;
    int R = r, C = c + (k + 2) * 2;
    vector<vector<int> > time(r, vector<int>(C, -1));
    queue<pair<int, int> > q;
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++) {
            char x; cin >> x;
            if(x == '#') {
                time[i][j + k] = 0;
                q.emplace(i, j + k);
            }
        }
    int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
    ll ans = 0;
    while(!q.empty()) {
        auto cr = q.front(); q.pop();
        int cx = cr.fi, cy = cr.se;
        if(time[cx][cy] == k) break;
        for(int mv = 0; mv < 8; mv++) {
            int nx = cx + dx[mv], ny = cy + dy[mv];
            if(nx >= 0 && nx < R && ny >= 0 && ny < C && time[nx][ny] == -1) time[nx][ny] = time[cx][cy] + 1, q.emplace(nx, ny);
        }
    }
    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            ans += (time[i][j] != -1);
        }
    }
    multiset<int> av;
    vector<vector<int> > to_add(C), to_del(C);
    for(int j = 0; j < C; j++) {
        if(time[0][j] == -1 || time[0][j] == k) continue;
        int step = k - time[0][j];
        to_add[j - step].pb(step);
        to_del[j + step].pb(step);
    }
    for(int j = 0; j < C; j++) {
        for(auto& x : to_add[j]) av.insert(x);
        ans += (!av.empty() ? (*av.rbegin()) : 0);
        for(auto& x : to_del[j]) av.erase(av.find(x));
        to_add[j].clear(); to_del[j].clear();
    }
    av.clear();
    for(int j = 0; j < C; j++) {
        if(time[r - 1][j] == -1 || time[r - 1][j] == k) continue;
        int step = k - time[r - 1][j];
        to_add[j - step].pb(step);
        to_del[j + step].pb(step);
    }
    for(int j = 0; j < C; j++) {
        for(auto& x : to_add[j]) av.insert(x);
        ans += (!av.empty() ? (*av.rbegin()) : 0);
        for(auto& x : to_del[j]) av.erase(av.find(x));
        to_add[j].clear(); to_del[j].clear();
    }
    cout << ans << '\n';
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) solve();

}

/*
KIVI
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3456kb

input:

5 5 3
.....
.###.
.#.#.
.###.
.....

output:

81

result:

ok single line: '81'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

3 3 1
#..
.#.
..#

output:

19

result:

ok single line: '19'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

4 6 3
..##..
.#..#.
.#..#.
..##..

output:

96

result:

ok single line: '96'

Test #4:

score: 0
Accepted
time: 1083ms
memory: 221944kb

input:

1 1 1000000
#

output:

4000004000001

result:

ok single line: '4000004000001'

Test #5:

score: 0
Accepted
time: 66ms
memory: 23764kb

input:

2 2 91011
.#
.#

output:

33132554552

result:

ok single line: '33132554552'

Test #6:

score: 0
Accepted
time: 1798ms
memory: 370284kb

input:

20 20 1000000
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
#############...

output:

4000080000400

result:

ok single line: '4000080000400'

Test #7:

score: 0
Accepted
time: 1067ms
memory: 235840kb

input:

20 20 630238
....................
....................
....................
....................
....................
....................
....................
....................
#...................
....................
....................
....................
....................
.................

output:

1588840081630

result:

ok single line: '1588840081630'

Test #8:

score: 0
Accepted
time: 1080ms
memory: 237088kb

input:

20 20 630238
#...................
.#..................
..#.................
...#................
....#...............
.....#..............
......#.............
.......#............
........#...........
.........#..........
..........#.........
...........#........
............#.......
.............#...

output:

1588850165636

result:

ok single line: '1588850165636'

Test #9:

score: 0
Accepted
time: 1801ms
memory: 370276kb

input:

20 20 1000000
.........##.........
........####........
.......######.......
......########......
.....##########.....
....############....
...##############...
..################..
.##################.
####################
####################
.##################.
..################..
...##########...

output:

4000080000220

result:

ok single line: '4000080000220'

Test #10:

score: 0
Accepted
time: 44ms
memory: 135884kb

input:

5 5 1000000
.....
.....
.....
.....
.....

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

5 5 1
.....
.....
.....
.....
.....

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 133ms
memory: 37168kb

input:

20 20 93002
####################
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#.................

output:

34604928576

result:

ok single line: '34604928576'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

20 20 3
####################
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#.....................

output:

532

result:

ok single line: '532'

Test #14:

score: 0
Accepted
time: 204ms
memory: 53404kb

input:

10 12 173312
...#....##..
....#.#.....
............
##.#..#.....
...#...#..#.
#..##.....#.
#.##.#..#...
....#....#.#
.#.#..#.....
............

output:

120155476561

result:

ok single line: '120155476561'

Test #15:

score: 0
Accepted
time: 11ms
memory: 7252kb

input:

16 1 12123
.
.
#
.
.
.
#
.
.
.
.
.
.
.
.
.

output:

588013997

result:

ok single line: '588013997'

Test #16:

score: 0
Accepted
time: 117ms
memory: 32152kb

input:

20 11 78669
........#..
#..........
##...#.....
.##........
...........
.....#....#
....#......
#.##.......
.##...#.#..
...........
###.#......
...#...#...
.#.........
...........
..........#
.........##
..#...#....
....#.....#
##.........
....###.#..

output:

24760123916

result:

ok single line: '24760123916'

Test #17:

score: 0
Accepted
time: 1062ms
memory: 222568kb

input:

3 20 935833
..#.#.....#...#.....
........#...........
.......#............

output:

3503163562228

result:

ok single line: '3503163562228'

Test #18:

score: 0
Accepted
time: 868ms
memory: 196392kb

input:

19 7 528014
.......
.....#.
#.#..#.
......#
.##...#
..#..#.
#..#...
.......
.#....#
.....#.
#......
#......
......#
..#....
...#.#.
.#..##.
....#.#
###..#.
...#...

output:

1115221537596

result:

ok single line: '1115221537596'

Test #19:

score: 0
Accepted
time: 191ms
memory: 48956kb

input:

15 15 139652
.............#.
...............
...............
...............
............#..
...............
.....#.........
.#........#...#
..#............
..##...........
...............
.#.............
.#.............
....#..........
...............

output:

78018544980

result:

ok single line: '78018544980'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

19 16 10
.#..............
.........#......
...#............
................
....#...#....#.#
.............#..
....#.........#.
.........#......
................
.....#..........
#..............#
......#.......#.
.......#........
........#....#..
.#......#.#.#...
#.........#.....
...#..........#.
.....

output:

1337

result:

ok single line: '1337'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

8 19 2
....#...........#..
....#.....##.......
.............#.....
#........###.......
............#......
........#.....#..#.
..#.....#..........
...................

output:

195

result:

ok single line: '195'

Test #22:

score: 0
Accepted
time: 1ms
memory: 3524kb

input:

15 1 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

0

result:

ok single line: '0'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

18 9 1
.........
......#..
........#
.........
......#..
#........
...#.....
.#...#.##
......#..
........#
..#....#.
.........
.......#.
#........
.#......#
.........
.........
.........

output:

111

result:

ok single line: '111'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

19 13 4
.........#...
........#....
..........###
.......##...#
.........#...
.............
.............
..#..........
.............
.............
.............
.......#.....
.............
..#...#......
.............
.............
.....##......
.............
....#........

output:

374

result:

ok single line: '374'

Test #25:

score: 0
Accepted
time: 1068ms
memory: 221896kb

input:

1 1 1000000
#

output:

4000004000001

result:

ok single line: '4000004000001'

Test #26:

score: 0
Accepted
time: 8ms
memory: 36648kb

input:

1 1 329048
.

output:

0

result:

ok single line: '0'

Test #27:

score: 0
Accepted
time: 19ms
memory: 7744kb

input:

20 20 12890
#..................#
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
..................

output:

665639639

result:

ok single line: '665639639'

Test #28:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

2 2 3901
.#
##

output:

60902415

result:

ok single line: '60902415'

Test #29:

score: 0
Accepted
time: 1060ms
memory: 235384kb

input:

20 20 630238
#...................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
.................

output:

1588850165294

result:

ok single line: '1588850165294'

Test #30:

score: 0
Accepted
time: 1095ms
memory: 235092kb

input:

20 20 630238
#..................#
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
.................

output:

1588826216592

result:

ok single line: '1588826216592'

Test #31:

score: 0
Accepted
time: 1076ms
memory: 236496kb

input:

20 20 630238
...................#
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
.................

output:

1588850165294

result:

ok single line: '1588850165294'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

8 8 2
........
........
.....#..
...##...
...#....
........
........
........

output:

44

result:

ok single line: '44'

Test #33:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

20 20 0
####################
##.#################
#########..###.#####
#########.#####.####
##.######.#.##.#####
######.##.##.#######
#############.######
######.#######.#####
##########.###..####
#####.##.#####.#####
#############.######
#####.###.##.#######
####################
##.##.####.....####...

output:

357

result:

ok single line: '357'