oj.uz

답안 #495626

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
495626 2021-12-19T15:27:40 Z Dirii Nafta (COI15_nafta) C++14
100 / 100
 419 ms 105744 KB 
// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define cll const ll
#define lp(a, b, c) for(ll a = b; a <= c; ++a)
#define lpd(a, b, c) for(ll a = b; a >= c; --a)
#define vec(a) vector<a>
#define pp(a, b) pair<a, b>
#define EACHCASE lpd(cs, read(), 1)
#define Fname "f"
using namespace std;

template <typename T> inline void Read(T &x){
    x = 0; char c;
    ll dau = 1;
    while(!isdigit(c = getchar())) if(c == '-') dau = -1;
    do{
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    x *= dau;
}

ll read(){
    ll tmp;
    cin >> tmp;
    return tmp;
}

void giuncute(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

void OF(){
    if(fopen(Fname".inp", "r")){
        freopen(Fname".inp", "r", stdin);
        freopen(Fname".out", "w", stdout);
    } else if(fopen(Fname".in", "r")){
        freopen(Fname".in", "r", stdin);
        freopen(Fname".out", "w", stdout);
    }
}

cll mxn = 2e3 + 4, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
ll n, m, a[mxn][mxn], cost[mxn][mxn] = {{0}}, dp[mxn][mxn] = {{0}};
vec(pp(pp(ll, ll), ll)) range;
bool d[mxn][mxn] = {{0}};

void sol(ll k, ll l, ll r, ll optL, ll optR){
    if(l > r) return;
    ll mid = (l + r) >> 1, optMid = -1;
    lp(i, optL, min(optR, mid)) if(dp[k - 1][i - 1] + cost[i][mid] > dp[k][mid]){
        dp[k][mid] = dp[k - 1][i - 1] + cost[i][mid],
        optMid = i;
    }
    sol(k, l, mid - 1, optL, optMid);
    sol(k, mid + 1, r, optMid, optR);
}

int main(){
    giuncute();
    #ifndef ONLINE_JUDGE
    OF();
    #endif
    cin >> n >> m;
    lp(i, 1, n) lp(j, 1, m){
        char c;
        cin >> c;
        if(c == '.') a[i][j] = -1;
        else a[i][j] = c - '0';
    }
    lp(i, 0, max(n, m) + 1) a[i][0] = a[0][i] = a[n + 1][i] = a[i][m + 1] = -1;
    lp(i, 1, n) lp(j, 1, m) if(~a[i][j] && !d[i][j]){
        // bfs
        queue<pp(ll, ll)> q;
        ll val = a[i][j];
        pp(ll, ll) res = {j, j};
        d[i][j] = 1;
        q.push({i, j});
        while(q.size()){
            ll u = q.front().first, v = q.front().second;
            q.pop();
            lp(i, 0, 3){
                ll nu = u + dx[i], nv = v + dy[i];
                if(~a[nu][nv] && !d[nu][nv]){
                    d[nu][nv] = 1;
                    val += a[nu][nv];
                    res.first = min(res.first, nv);
                    res.second = max(res.second, nv);
                    q.push({nu, nv});
                }
            }
        }
        range.push_back({res, val});
    }
    sort(range.begin(), range.end(), [](pp(pp(ll, ll), ll) &x, pp(pp(ll, ll), ll) &y){
        return x.first.second < y.first.second;
    });
    ll cur = -1;
    lp(_right, 1, m){
        while(cur < (ll)range.size() - 1 && range[cur + 1].first.second <= _right)
            ++cur,
            cost[range[cur].first.first][_right] += range[cur].second;
        lp(i, 1, _right) 
            cost[i][_right] += cost[i - 1][_right] + cost[i][_right - 1] - cost[i - 1][_right - 1],
            dp[1][_right] = max(dp[1][_right], cost[i][_right]);
    }
    lp(i, 2, m) sol(i, 1, m, 1, m);
    lp(i, 1, m) cout << dp[i][m] << '\n';
}

Compilation message

nafta.cpp: In function 'void OF()':
nafta.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(Fname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(Fname".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 968 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 976 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 968 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 976 KB Output is correct
7 Correct 9 ms 6736 KB Output is correct
8 Correct 11 ms 6612 KB Output is correct
9 Correct 10 ms 6356 KB Output is correct
10 Correct 9 ms 6676 KB Output is correct
11 Correct 9 ms 6500 KB Output is correct
12 Correct 8 ms 6352 KB Output is correct

Subtask #3
66.0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 968 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 976 KB Output is correct
7 Correct 9 ms 6736 KB Output is correct
8 Correct 11 ms 6612 KB Output is correct
9 Correct 10 ms 6356 KB Output is correct
10 Correct 9 ms 6676 KB Output is correct
11 Correct 9 ms 6500 KB Output is correct
12 Correct 8 ms 6352 KB Output is correct
13 Correct 352 ms 105744 KB Output is correct
14 Correct 419 ms 99932 KB Output is correct
15 Correct 377 ms 94372 KB Output is correct
16 Correct 280 ms 99688 KB Output is correct
17 Correct 325 ms 94112 KB Output is correct
18 Correct 282 ms 93900 KB Output is correct