제출 #495626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
495626		Dirii	Nafta (COI15_nafta)	C++14	100 / 100	419 ms	105744 KiB

nafta

// #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';
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66