Submission #1099719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099719		Zero_OP	Nafta (COI15_nafta)	C++14	100 / 100	269 ms	117760 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"

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

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

using ll = long long;
using ld = long double;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }

const int MAX = 2e3 + 5;
const int di[4] = {-1, +1, 0, 0};
const int dj[4] = {0, 0, +1, -1};

int n, m, cc;
bool vis[MAX][MAX], used[MAX * MAX];
char a[MAX][MAX];
int v[MAX], dp[2][MAX], sum[MAX * MAX], min_column[MAX * MAX], id[MAX][MAX], cost[MAX][MAX];

bool inside(int i, int j){
    return 1 <= i && i <= n && 1 <= j && j <= m;
}

void dfs(int i, int j){
    vis[i][j] = true;
    sum[cc] += (a[i][j] - '0');
    min_column[cc] = min(min_column[cc], j);
    id[i][j] = cc;

    for(int x = 0; x < 4; ++x){
        int ni = i + di[x], nj = j + dj[x];
        if(inside(ni, nj) && !vis[ni][nj] && a[ni][nj] != '.'){
            dfs(ni, nj);
        }
    }
}

void solve(int l, int r, int optL, int optR){
    if(l > r) return;

    int mid = l + r >> 1;
    int optMid = optL;
    for(int i = optL; i <= min(optR, mid); ++i){
        if(maximize(dp[1][mid], dp[0][i - 1] + cost[mid][i])){
            optMid = i;
        }
    }

    solve(l, mid - 1, optL, optMid);
    solve(mid + 1, r, optMid, optR);
}

void testcase(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> a[i][j];
        }
    }

    memset(min_column, 0x3f, sizeof(min_column));
    cc = 0;

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(!vis[i][j] && a[i][j] != '.'){
                ++cc; dfs(i, j);
                //cout << dbg(sum[cc]) << '\n';
            }
        }
    }

    for(int j = 1; j <= m; ++j){
        vector<int> used_cc;
        fill(v + 1, v + 1 + m, 0);
        for(int i = 1; i <= n; ++i){
            if(id[i][j] != 0){
                if(!used[id[i][j]]){
                    used_cc.push_back(id[i][j]);
                    used[id[i][j]] = true;
                }
            }
        }

        for(int u : used_cc){
            used[u] = false;
        }

        sort(all(used_cc), [&](int i, int j){ return min_column[i] < min_column[j]; });

        int total = 0;
        for(int k = j; k >= 1; --k){
            while(!used_cc.empty() && k <= min_column[used_cc.back()]){
                total += sum[used_cc.back()];
                used_cc.pop_back();
            }

            cost[j][k] = total;
        }
    }

    dp[0][0] = 0;
    for(int i = 1; i <= m; ++i) dp[0][i] = -1e9;

    for(int k = 1; k <= m; ++k){
        for(int i = 0; i <= m; ++i){
            dp[1][i] = -1e9;
        }

        solve(1, m, 1, m);
        cout << *max_element(dp[1] + 1, dp[1] + 1 + m) << '\n';
        for(int i = 1; i <= m; ++i){
            dp[0][i] = dp[1][i];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    int T = 1; //cin >> T;
    while(T--) testcase();

    return 0;
}

Compilation message (stderr)

nafta.cpp: In function 'bool minimize(T&, const T&)':
nafta.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
nafta.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
nafta.cpp: In function 'bool maximize(T&, const T&)':
nafta.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if(a < b) return a = b, true; return false;
      |     ^~
nafta.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
nafta.cpp: In function 'void solve(int, int, int, int)':
nafta.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = l + r >> 1;
      |               ~~^~~
nafta.cpp: In function 'int main()':
nafta.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(filename".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66