oj.uz

Submission #1099719

# Submission time Handle Problem Language Result Execution time Memory
1099719 2024-10-12T04:51:40 Z Zero_OP Nafta (COI15_nafta) C++14
100 / 100
 269 ms 117760 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16732 KB Output is correct
2 Correct 7 ms 16824 KB Output is correct
3 Correct 7 ms 16720 KB Output is correct
4 Correct 7 ms 16732 KB Output is correct
5 Correct 7 ms 16732 KB Output is correct
6 Correct 7 ms 16736 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16732 KB Output is correct
2 Correct 7 ms 16824 KB Output is correct
3 Correct 7 ms 16720 KB Output is correct
4 Correct 7 ms 16732 KB Output is correct
5 Correct 7 ms 16732 KB Output is correct
6 Correct 7 ms 16736 KB Output is correct
7 Correct 12 ms 20316 KB Output is correct
8 Correct 14 ms 20288 KB Output is correct
9 Correct 14 ms 21600 KB Output is correct
10 Correct 14 ms 19616 KB Output is correct
11 Correct 11 ms 19548 KB Output is correct
12 Correct 12 ms 19548 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16732 KB Output is correct
2 Correct 7 ms 16824 KB Output is correct
3 Correct 7 ms 16720 KB Output is correct
4 Correct 7 ms 16732 KB Output is correct
5 Correct 7 ms 16732 KB Output is correct
6 Correct 7 ms 16736 KB Output is correct
7 Correct 12 ms 20316 KB Output is correct
8 Correct 14 ms 20288 KB Output is correct
9 Correct 14 ms 21600 KB Output is correct
10 Correct 14 ms 19616 KB Output is correct
11 Correct 11 ms 19548 KB Output is correct
12 Correct 12 ms 19548 KB Output is correct
13 Correct 196 ms 59916 KB Output is correct
14 Correct 257 ms 58636 KB Output is correct
15 Correct 269 ms 117760 KB Output is correct
16 Correct 187 ms 54880 KB Output is correct
17 Correct 206 ms 53588 KB Output is correct
18 Correct 190 ms 53588 KB Output is correct