Submission #1146038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146038		hoa208	Nafta (COI15_nafta)	C++20	0 / 100	1 ms	1088 KiB

nafta

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
#define t_test int t;cin >> t;while(t--)
const ll mod = 1e9 + 7;
const ll INF = 1e17;
const ll N = 2003;
ll r, s;
char a[N][N];
namespace subX {
    ll mark[N][N];
    pa mov[] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    bool outside(ll x, ll y) {
        return x <= 0 || x > r || y <= 0 || y > s;
    }
    void dfs(pa u, ll &l, ll &r, ll &sum) {
        mark[u.fi][u.se] = 1;
        l = min(l, u.se);
        r = max(u.se, r);
        sum += a[u.fi][u.se] - '0';
        FOR(i, 0, 3) {
            pa v = {mov[i].fi + u.fi, mov[i].se + u.se};
            if(outside(v.fi, v.se) || a[v.fi][v.se] == '.' || mark[v.fi][v.se]) continue;
            dfs(v, l, r, sum);
        }
    }
    ll cost[N][N], cnt[N], dp[N][N], best[N];
    vector<pa> vt[N];
    void dnc(ll g, ll l, ll r, ll u, ll v) {
        if(l > r) return;
        ll mid = l + r >> 1;
        ll index = 0;
        FOR(i, u, v) {
            ll val = dp[i - 1][g - 1] + cost[i][mid];
            if(dp[mid][g] < val) {
                dp[mid][g] = val;
                index = i;
            }
        }
        best[g] = max(dp[mid][g], best[g]);
        dnc(g, l, mid - 1, u, index);
        dnc(g, mid + 1, r, index, v);
    }
    void slove() {
        FOR(i, 1, r) {
            FOR(j, 1, s) {
                if(!mark[i][j] && a[i][j] != '.') {
                    ll _l = j, _r = j, sum = 0;
                    dfs({i, j}, _l, _r, sum);
                    vt[_l].push_back({_r, sum});
                }
            }
        }
        FORD(j, s, 1) {
            for(auto v : vt[j]) {
                FOR(i, j, v.fi) {
                    cnt[i] += v.se;
                }
            }
            FOR(i, j, s) {
                cost[j][i] = cnt[i];    
            }
        }
        FOR(i, 1, s) {
            dnc(i, 1, s, 1, s);
        }
        FOR(i, 1, s) {
            cout << best[i] << '\n';
        }
    }
}

void hbmt() {
    // inp
    cin >> r >> s;
    FOR(i, 1, r) {
        FOR(j, 1, s) {
            cin >> a[i][j];
        }
    }

    // slove
    return subX::slove();
}

int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    if(fopen("hbmt.inp", "r")) {
        freopen("hbmt.inp", "r", stdin);
        freopen("hbmt.out", "w", stdout);
    }
    
    // t_test 
    hbmt();
    return 0;
}

Compilation message (stderr)

nafta.cpp: In function 'int main()':
nafta.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("hbmt.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen("hbmt.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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