oj.uz

Submission #416756

# Submission time Handle Problem Language Result Execution time Memory
416756 2021-06-02T21:49:09 Z JerryLiu06 Nafta (COI15_nafta) C++17
100 / 100
 416 ms 84288 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using db = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#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(a, x) for (auto& a : x)
 
const int MOD = 1e9 + 7;
const int MX = 2e3 + 10;
const ll INF = 1e18;

int R, S; string grid[MX]; int pref[MX][MX];

pi bound; int sum, tot; bool vis[MX][MX]; int DP[MX][MX];

void DFS(int x, int y) {
    if (x < 0 || x >= R || y < 0 || y >= S || vis[x][y] || grid[x][y] == '.') return ;

    bound.f = min(bound.f, y); bound.s = max(bound.s, y); vis[x][y] = true; sum += grid[x][y] - '0';

    DFS(x + 1, y); DFS(x, y + 1); DFS(x - 1, y); DFS(x, y - 1); 
}

void solve(int k, int l, int r, int optl, int optr) {
    if (l > r) return ; int mid = (l + r) / 2; pi BEST = {MOD, -1};

    FOR(i, optl, min(mid, optr) + 1) {
        BEST = min(BEST, {DP[i][k - 1] + pref[i + 1][mid - 1], i});
    }
    DP[mid][k] = BEST.f; int opt = BEST.s;

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

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

    cin >> R >> S; F0R(i, R) cin >> grid[i];

    F0R(i, R) F0R(j, S) if (grid[i][j] != '.' && !vis[i][j]) {
        bound = {MOD, -MOD}; sum = 0; DFS(i, j); pref[bound.f + 1][bound.s + 1] += sum; tot += sum;
    }
    ROF(i, 1, S + 1) FOR(j, 1, S + 1) {
        pref[i][j] += pref[i + 1][j]; pref[i][j] += pref[i][j - 1];

        pref[i][j] -= pref[i + 1][j - 1]; // Overcount by PIE
    }
    FOR(i, 1, S + 2) DP[i][0] = MOD;

    FOR(k, 1, S + 2) {
        solve(k, 0, S + 1, 0, S); int ans = 0;

        if (k > 1) cout << tot - DP[S + 1][k] << "\n";
    }
}

Compilation message

nafta.cpp: In function 'void solve(int, int, int, int, int)':
nafta.cpp:61:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   61 |     if (l > r) return ; int mid = (l + r) / 2; pi BEST = {MOD, -1};
      |     ^~
nafta.cpp:61:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   61 |     if (l > r) return ; int mid = (l + r) / 2; pi BEST = {MOD, -1};
      |                         ^~~
nafta.cpp: In function 'int main()':
nafta.cpp:87:39: warning: unused variable 'ans' [-Wunused-variable]
   87 |         solve(k, 0, S + 1, 0, S); int ans = 0;
      |                                       ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 892 KB Output is correct
6 Correct 1 ms 844 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 892 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 7 ms 4172 KB Output is correct
8 Correct 8 ms 4196 KB Output is correct
9 Correct 9 ms 5276 KB Output is correct
10 Correct 6 ms 4172 KB Output is correct
11 Correct 6 ms 4236 KB Output is correct
12 Correct 7 ms 4284 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 892 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 7 ms 4172 KB Output is correct
8 Correct 8 ms 4196 KB Output is correct
9 Correct 9 ms 5276 KB Output is correct
10 Correct 6 ms 4172 KB Output is correct
11 Correct 6 ms 4236 KB Output is correct
12 Correct 7 ms 4284 KB Output is correct
13 Correct 331 ms 43920 KB Output is correct
14 Correct 364 ms 43948 KB Output is correct
15 Correct 416 ms 84288 KB Output is correct
16 Correct 291 ms 43944 KB Output is correct
17 Correct 355 ms 43840 KB Output is correct
18 Correct 337 ms 43940 KB Output is correct