Submission #1164754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164754		spycoderyt	Nafta (COI15_nafta)	C++20	100 / 100	234 ms	94780 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
char A[N][N];
int sum[N][N],vis[N][N];
int cur = 0,l,r;
int temp[N];
// int dp[N][N]; // for index 1...i, whats the most given that u choose k times and you also choose the i'th
int dp[2][N];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int n,m;
vector<pair<int,int> > v[N];
int get(int l,int r) {return sum[l][r] - sum[r+1][r+1];}
void solve(int l,int r,int optl,int optr) {
    if(l>r)return;
    int mid = (l+r)/2;
    pair<int,int> mx = make_pair(0,-1);
    for(int i = optl;i<=min(optr,mid);i++){
        mx = max(mx,{dp[0][i-1] + get(i,mid), i});
    }
    int idx = mx.second;
    dp[1][mid] = mx.first;
    solve(l,mid-1,optl,idx);
    solve(mid+1,r,idx,optr);
}
void dfs(int x,int y) {
    cur+=A[x][y] - '0';
    vis[x][y] = 1;
    l = min(l,y);
    r = max(r,y);
    for(int i = 0;i<4;i++) {
        int X = x + dx[i], Y = y + dy[i];
        if(X>=1 && Y>=1 && X<=n && Y<=m && !vis[X][Y] && !(A[X][Y] == '.'))dfs(X,Y);
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    char c;
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin>>c;
            A[i][j]=c;
        }
    }
    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=m;j++) {
            if(vis[i][j] || A[i][j] == '.')continue;
            l = r = j;
            cur = 0;
            dfs(i,j);
            v[l].push_back({r,cur});
        }
    }
    for(int i = m;i>=0;i--){
        for(auto [x,val] : v[i])temp[x]+=val;
        for(int j = m;j>=i;j--){
            sum[i][j] = sum[i][j+1] + temp[j];
        }
    }
    // sum[x][y] is sum of components that have l>=x and r>=y
    for(int i = 1;i<=m;i++) {
        solve(i,m,i,m);
        int ans = 0;
        for(int j = 1;j<=m;j++)ans=max(ans,dp[1][j]);
        cout<<ans<<"\n";
        swap(dp[0],dp[1]);
    }

}

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