Submission #780921

#	Time	Username	Problem	Language	Result	Execution time	Memory
780921		Ivkosqn	Nafta (COI15_nafta)	C++14	11 / 100	1065 ms	2388 KiB

nafta

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int maxn = 2010;
int n, m, used[maxn][maxn];
char c[maxn][maxn];
vector<long long> dp_bef(maxn), dp_aft(maxn);

struct cell{
    int x, y;

    cell operator+(cell c){
        return {x + c.x, y + c.y};
    }

    bool inRange(){
        return x >= 1 && x <= n && y >= 1 && y <= m;
    }
};

cell dir[4] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };

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

void bfs(cell beg, int col){
    queue<cell> q;
    q.push(beg);
    used[beg.x][beg.y] = col;
    while(!q.empty()){
        cell e = q.front();
        q.pop();
        for(int i = 0;i < 4;i++){
            cell curr = e + dir[i];
            if(!curr.inRange() || used[curr.x][curr.y])
                continue;
            if(c[curr.x][curr.y] == '.')
                continue;
            used[curr.x][curr.y] = col;
            q.push(curr);
        }
    }
}

void preCompute(){
    int cnt = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(c[i][j] != '.' && !used[i][j]){
                bfs({i, j}, cnt);
                cnt++;
            }
        }
    }
    assert(cnt <= 2000);
    memset(used, 0, sizeof(used));
}

int cycle = 1, s;

long long calc(int i, int mid){
    long long sum = 0;
    queue<cell> q;
    cycle++;
    for(int j = 1;j <= n;j++){
        if(mid <= m && c[j][mid] != '.'){
            q.push({j, mid});
            used[j][mid] = cycle;
            sum += c[j][mid] - '0';
        }
    }
    s = sum;
    while(!q.empty()){
        cell t = q.front();
        q.pop();
        for(int j = 0;j < 4;j++){
            cell curr = dir[j] + t;
            if(!curr.inRange() || used[curr.x][curr.y] == cycle)
                continue;
            if(c[curr.x][curr.y] == '.' || curr.y > mid || curr.y <= i)
                continue;
            sum += c[curr.x][curr.y] - '0';
            q.push(curr);
            used[curr.x][curr.y] = cycle;
        }
    }
    if(i == 0)
        return sum;
    q = queue<cell>();
    for(int j = 1;j <= n;j++){
        if(c[j][i] != '.' && used[j][i] != cycle){
            q.push({j, i});
            used[j][i] = cycle;
        }
    }
    while(!q.empty()){
        cell t = q.front();
        q.pop();
        for(int j = 0;j < 4;j++){
            cell curr = dir[j] + t;
            if(!curr.inRange() || used[curr.x][curr.y] == cycle)
                continue;
            if(c[curr.x][curr.y] == '.' || curr.y > mid || curr.y <= i)
                continue;
            sum += c[curr.x][curr.y] - '0';
            q.push(curr);
            used[curr.x][curr.y] = cycle;
        }
    }
    return sum;
}

void divide(int l, int r, int optl, int optr){
    if(l > r)
        return;
    int mid = (l + r) / 2;
    long long best = LLONG_MIN, k;
    for(int i = optl;i <= min(mid, optr);i++){
        long long curr = dp_bef[i - 1] + calc(i - 1, mid);
        if(curr > best){
            best = curr;
            k = i;
        }
    }
    dp_aft[mid] = best;
    divide(l, mid - 1, optl, k);
    divide(mid + 1, r, k, optr);
}


void solve(){
    long long ans = 0;
    for(int i = 1;i <= m;i++){
        dp_bef[i] = calc(0, i);
        ans = max(ans, dp_bef[i] + calc(i, m + 1) - s);
    }
    cout << ans << endl;
    for(int i = 2;i <= m;i++){
        divide(1, m, 1, m);
        dp_bef = dp_aft;
        long long ans = 0;
        for(int i = 1;i <= m;i++){
            ans = max(ans, dp_aft[i] + calc(i, m + 1) - s);
        }
        cout << ans << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    read();
    solve();
    return 0;
}

Compilation message (stderr)

nafta.cpp: In function 'void divide(int, int, int, int)':
nafta.cpp:134:11: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  134 |     divide(l, mid - 1, optl, k);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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