Submission #1325971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325971		Robert_junior	Nafta (COI15_nafta)	C++20	100 / 100	463 ms	103132 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define pii pair<int, int>
const int N = 2000 + 100, inf = 1e18 ;
char a[N][N];
int R, C;
int dp[N][N], I[N][N], vis[N][N], pf[N];
int cost(int l, int r){
    if(l > r) return 0;
    return pf[r] - I[l - 1][r];
}
void dc(int k, int l, int r, int optl, int optr){
    if(l > r) return;
    int m = (l + r) / 2;
    dp[k][m] = dp[k - 1][m];
    int opt = optl;
    for(int i = optl; i <= min(m, optr); i++){
        if(dp[k][m] < dp[k - 1][i - 1] + cost(i, m)){
            dp[k][m] = dp[k - 1][i - 1] + cost(i, m);
            opt = i;
        }
    }
    dc(k, l, m - 1, optl, opt);
    dc(k, m + 1, r, opt, optr);
}
bool ok(int i, int j){
    if(i < 1 || j < 1 || i > R || j > C || a[i][j] == '.' || vis[i][j]) return false;
    return true;
}
main(){
    cin>>R>>C;
    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++){
            cin>>a[i][j]; 
        }
    }
    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++){
            if(a[i][j] == '.' || vis[i][j]) continue;
            queue<pair<int, int>>qu;
            qu.push({i, j}); 
            int sum = 0;
            int l = j, r = j;
            while(qu.size()){
                auto [x, y] = qu.front();
                qu.pop();
                //cout<<x<<' '<<y<<' '<<ok(x, y)<<'\n';
                if(!ok(x, y)) continue;
                vis[x][y] = 1;
                sum += a[x][y] - '0';
                qu.push({x - 1, y});
                qu.push({x + 1, y});
                qu.push({x, y + 1});
                qu.push({x, y - 1});
                l = min(l, y);
                r = max(r, y);
            }
            pf[l] += sum;
            pf[r + 1] -= sum;
            for(int k = l; k <= r; k++){
                I[k][l] += sum;
                I[k][r + 1] -= sum;
            }
        }
    }
    {
        for(int i = 1; i <= C; i++){
            pf[i] += pf[i - 1];
        }
        for(int i = 1; i <= C; i++){
            for(int j = 1; j <= C; j++){
                I[i][j] += I[i][j - 1];
            }
        }
    }
    for(int i = 1; i <= C; i++){
        dp[1][i] = pf[i];
    }
    for(int i = 2; i <= C; i++){
        dc(i, 1, C, 1, C);
    }
    for(int i = 1; i <= C; i++){
        cout<<*max_element(dp[i] + 1, dp[i] + C + 1)<<'\n';
    }
}

Compilation message (stderr)

nafta.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      | ^~~~

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