oj.uz

Submission #673671

# Submission time Handle Problem Language Result Execution time Memory
673671 2022-12-21T16:05:11 Z vjudge1 Nafta (COI15_nafta) C++11
100 / 100
 307 ms 140652 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

const int MOD = 1e9 + 7;
const ll INF = 1e18;

const int MX = 2005;

int N, M;

V<pi> lst[MX];
bool vis[MX][MX];

str s[MX];

bool isInside(int r, int c) {
    return min(r, c) >= 1 && r <= N && c <= M;
}

void dfs(int row, int col, int &l, int &r, int &sum) {
    vis[row][col] = true;
    sum += s[row][col] - '0';
    ckmin(l, col);
    ckmax(r, col);
    F0R(i, 4) {
        int nrow = row + dx[i], ncol = col + dy[i];
        if(isInside(nrow, ncol) && !vis[nrow][ncol] && s[nrow][ncol] != '.') {
            dfs(nrow, ncol, l, r, sum);
        }
    }
}

int cursum[MX];
int cost[MX][MX];

int dp[MX][MX];

void dnc(int k, int l, int r, int optl, int optr) {
    if(l > r) return;
    int mid = (l + r) >> 1;
    dp[k][mid] = -MOD;
    int opt = -1;
    FOR(j, optl, min(mid,optr)+1) if(ckmax(dp[k][mid], dp[k-1][j] + cost[j][mid])) {
        opt = j;
    }

    dnc(k, l, mid-1, optl, opt);
    dnc(k, mid+1, r, opt, optr);
}

void solve() {
    cin >> N >> M;
    FOR(i,1,N+1) {
        cin >> s[i];
        s[i] = '$' + s[i];
    }
    FOR(i,1,N+1) FOR(j,1,M+1) if(!vis[i][j] && s[i][j] != '.') {
        int l, r, sum;
        l = MOD, r = -MOD, sum = 0;
        dfs(i, j, l, r, sum);
        lst[r].pb({l, sum});
    }
    ROF(i,1,M+1) {
        each(p, lst[i]) {
            ROF(j, p.fi, i+1) {
                cursum[j] += p.se;
            }
        }
        R0F(j, i+1) {
            cost[j][i] = cursum[i] - cursum[j];
        }
    }
    memset(dp, -0x3f, sizeof dp);
    dp[0][0] = 0;
    FOR(k,1,M+1) {
        dnc(k, 1, M, 0, M-1);
        int res = -MOD;
        FOR(i,1,M+1) ckmax(res, dp[k][i]);
        cout << res << nl;
    }
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

nafta.cpp: In function 'void setIO(std::string)':
nafta.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16468 KB Output is correct
2 Correct 6 ms 16468 KB Output is correct
3 Correct 7 ms 16468 KB Output is correct
4 Correct 6 ms 16468 KB Output is correct
5 Correct 6 ms 16468 KB Output is correct
6 Correct 7 ms 16444 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16468 KB Output is correct
2 Correct 6 ms 16468 KB Output is correct
3 Correct 7 ms 16468 KB Output is correct
4 Correct 6 ms 16468 KB Output is correct
5 Correct 6 ms 16468 KB Output is correct
6 Correct 7 ms 16444 KB Output is correct
7 Correct 13 ms 18504 KB Output is correct
8 Correct 13 ms 18456 KB Output is correct
9 Correct 14 ms 20560 KB Output is correct
10 Correct 11 ms 18388 KB Output is correct
11 Correct 10 ms 18388 KB Output is correct
12 Correct 10 ms 18260 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16468 KB Output is correct
2 Correct 6 ms 16468 KB Output is correct
3 Correct 7 ms 16468 KB Output is correct
4 Correct 6 ms 16468 KB Output is correct
5 Correct 6 ms 16468 KB Output is correct
6 Correct 7 ms 16444 KB Output is correct
7 Correct 13 ms 18504 KB Output is correct
8 Correct 13 ms 18456 KB Output is correct
9 Correct 14 ms 20560 KB Output is correct
10 Correct 11 ms 18388 KB Output is correct
11 Correct 10 ms 18388 KB Output is correct
12 Correct 10 ms 18260 KB Output is correct
13 Correct 202 ms 48828 KB Output is correct
14 Correct 263 ms 45652 KB Output is correct
15 Correct 307 ms 140652 KB Output is correct
16 Correct 178 ms 45004 KB Output is correct
17 Correct 233 ms 42136 KB Output is correct
18 Correct 207 ms 41964 KB Output is correct