Submission #1084383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084383		vjudge1	Nafta (COI15_nafta)	C++17	100 / 100	312 ms	106440 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array

const int LOG = 20;
const int MOD = 1e9 + 7;
const int INF = 1e18;

const int N = 3005;

int n, m;
string s[N];
int mx, mn, sum;
void dfs(int x,int y){
    if(x  < 0 || x >= n || y < 0 || y >= m || s[x][y] == '.')return;
    mn = min(mn, y);
    mx = max(mx, y);
    sum += s[x][y] - '0';
    s[x][y] = '.';
    dfs(x + 1, y);dfs(x - 1, y);
    dfs(x, y + 1);dfs(x, y - 1);
}

namespace fewwy{
    int bit[N];
    void upd(int i,int v){
        for(i++;i < N;i += i & -i)bit[i] += v;
    }

    int qry(int i){
        int ans = 0;
        for(i++;i;i -= i & -i)ans += bit[i];
        return ans;
    }

    int qry(int l,int r){
        return qry(r) - qry(l - 1);
    }
};
int C[N][N];
int dp[N][N];

void f(int l,int r,int tl,int tr,int j){
    if(l > r)return;
    int tm = (l+ r) / 2;
    int opt = tl;
    for(int i = tl;i <= min(tm, tr);i++){
        if(dp[i - 1][j - 1] + C[i][tm] > dp[tm][j]){
            dp[tm][j] = dp[i - 1][j - 1] + C[i][tm];
            opt = i;
        }
    }
    f(l, tm - 1, tl, opt, j);
    f(tm + 1, r, opt, tr, j);
}

bool comp(ar<int, 3> a, ar<int, 3> b ){
    return a[1] < b[1];
}

void skibidisigmaohiorizz(vector<ar<int, 3>> &e){
    sort(e.begin(), e.end(), comp);
    for(auto [l, r, v]: e)fewwy::upd(l, v);
    int k = 0;
    for(int j = 1;j <= m;j++){
        while(k < e.size() && e[k][1] < j){
            fewwy::upd(e[k][0], -e[k][2]);
            ++k;
        }
        for(int i = 1;i <= j;i++)C[i][j] = fewwy::qry(i, j);
    }
}

signed main() {
    cin>>n>>m;
    for(int i = 0;i < n;i++)cin>>s[i];
    vector<ar<int, 3> > e;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(s[i][j] == '.')continue;
            sum = 0, mx = j, mn = j;
            dfs(i, j);
            e.push_back({++mn, ++mx, sum});
        }
    }
    skibidisigmaohiorizz(e);
    for(int i = 1;i <= m;i++){
        f(1, m, 1, m, i);
        int mx = 0;
        for(int j = 1;j <= m;j++)mx = max(mx, dp[j][i]);
        cout<<mx<<'\n';
    }
}

Compilation message (stderr)

nafta.cpp: In function 'void skibidisigmaohiorizz(std::vector<std::array<long long int, 3> >&)':
nafta.cpp:68:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(k < e.size() && e[k][1] < j){
      |               ~~^~~~~~~~~~

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