oj.uz

Submission #773062

# Submission time Handle Problem Language Result Execution time Memory
773062 2023-07-04T14:33:17 Z hafo Nafta (COI15_nafta) C++14
100 / 100
 306 ms 60152 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2000 + 7;
const ll oo = 1e18 + 69;

int n, m, id[maxn][maxn], num_gr = 0, cost[maxn][maxn], dp[maxn][maxn];
char a[maxn][maxn];
struct group {
    int l, r, oil;
};
vector<group> cpn;
pa d[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool used[2000 * 2000 + 7];

void bfs(int sx, int sy) {
    id[sx][sy] = ++num_gr;
    queue<pa> q;
    q.push({sx, sy});
    int s = 0, l = m, r = 0;

    while(!q.empty()) {
        int u = q.front().fi, v = q.front().se;
        q.pop();

        s += a[u][v] - '0';
        mini(l, v);
        maxi(r, v);

        for(int k = 0; k < 4; k++) {
            int x = u + d[k].fi, y = v + d[k].se;
            if(x < 1 || x > n || y < 1 || y > m || id[x][y] || a[x][y] == '.') continue;
            id[x][y] = num_gr;
            q.push({x, y});
        }
    }
    cpn.pb({l, r, s});
}

void solve(int t, int l, int r, int optl, int optr) {
    if(l > r) return;
    int i = l + r >> 1;
    pa res = {0, 0};
    for(int j = optl; j <= min(i - 1, optr); j++) 
        if(maxi(res.fi, dp[t - 1][j] + cost[i][j])) res.se = j;
    dp[t][i] = res.fi;
    solve(t, l, i - 1, optl, res.se);
    solve(t, i + 1, r, res.se, optr);
} 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) cin>>a[i][j];
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(id[i][j] || a[i][j] == '.') continue;
            bfs(i, j);
        }
    }

    for(int i = 1; i <= m; i++) {
        vector<pa> val;
        for(int j = 1; j <= n; j++) {
            if(!id[j][i]) continue;
            int idd = id[j][i] - 1;
            if(used[idd]) continue;
            used[idd] = 1;
            val.pb({cpn[idd].l, idd});
            cost[i][0] += cpn[idd].oil;
        }

        sort(all(val));
        for(auto i:val) used[i.se] = 0;
        int k = 0;
        for(int j = 1; j < i; j++) {
            cost[i][j] = cost[i][j - 1];
            while(k < Size(val) && val[k].fi == j) {
                cost[i][j] -= cpn[val[k].se].oil;
                k++;
            }
        }
    }

    for(int t = 1; t <= m; t++) {
        int ans = 0;
        if(t == 1) {
            for(int i = 1; i <= m; i++) dp[t][i] = cost[i][0];
        } else solve(t, 1, m, 1, m);
        for(int i = 1; i <= m; i++) maxi(ans, dp[t][i]);
        cout<<ans<<"\n";
    }
    return 0;
}

Compilation message

nafta.cpp: In function 'void solve(int, int, int, int, int)':
nafta.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int i = l + r >> 1;
      |             ~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 7 ms 5776 KB Output is correct
8 Correct 8 ms 5596 KB Output is correct
9 Correct 9 ms 5460 KB Output is correct
10 Correct 6 ms 4820 KB Output is correct
11 Correct 6 ms 4692 KB Output is correct
12 Correct 6 ms 4708 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 7 ms 5776 KB Output is correct
8 Correct 8 ms 5596 KB Output is correct
9 Correct 9 ms 5460 KB Output is correct
10 Correct 6 ms 4820 KB Output is correct
11 Correct 6 ms 4692 KB Output is correct
12 Correct 6 ms 4708 KB Output is correct
13 Correct 261 ms 60152 KB Output is correct
14 Correct 304 ms 56856 KB Output is correct
15 Correct 293 ms 53864 KB Output is correct
16 Correct 244 ms 52812 KB Output is correct
17 Correct 306 ms 49812 KB Output is correct
18 Correct 235 ms 49768 KB Output is correct