oj.uz

Submission #428158

# Submission time Handle Problem Language Result Execution time Memory
428158 2021-06-15T08:31:37 Z fvogel499 Nafta (COI15_nafta) C++14
100 / 100
 740 ms 212956 KB 
/*
File created on 06/14/2021 at 18:59:52.
Link to problem: https://oj.uz/problem/view/COI15_nafta
Description: 
Time complexity: O()
Space complexity: O()
Status: DEV
Copyright: Ⓒ 2021 Francois Vogel
*/

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define mp pair<pii, int>
#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define ins insert
#define cls clear

#define int ll
#define ll long long

const int siz = 2000+3;
const pii dirs [4] = {pii(0, 1), pii(0, -1), pii(1, 0), pii(-1, 0)};

int height, width;
int grid [siz][siz];
bool as [siz][siz];
int countIntervals [siz][siz];
int jNotI [siz][siz];
int dp [siz][siz];

mp dfs(int i, int j) {
    mp res = mp(pii(j, j), grid[i][j]);
    as[i][j] = true;
    for (pii dir : dirs) {
        int ni = i+dir.f;
        int nj = j+dir.s;
        if (0 <= ni and 0 <= nj and ni < height and nj < width and !as[ni][nj] and grid[ni][nj] != -1) {
            mp nRes = dfs(ni, nj);
            res.f.f = min(res.f.f, nRes.f.f);
            res.f.s = max(res.f.s, nRes.f.s);
            res.s += nRes.s;
        }
    }
    return res;
}

pii bestChoice(int mid, int& kConst, int scopeBegin, int scopeEnd) {
    int best = width;
    int bestScore = 0;
    for (int i = max(mid+1, scopeBegin); i <= scopeEnd; i++) {
        if (best == width or dp[i][kConst-1]+jNotI[mid][i] > bestScore) {
            best = i;
            bestScore = dp[i][kConst-1]+jNotI[mid][i];
        }
    }
    return pii(best, bestScore);
}

void compute(int start, int end, int scopeBegin, int scopeEnd, int& kConst) {
    if (end < start) return;
    int mid = (start+end)/2;
    pii res = bestChoice(mid, kConst, scopeBegin, scopeEnd);
    dp[mid][kConst] = res.s;
    compute(start, mid-1, scopeBegin, res.f, kConst);
    compute(mid+1, end, res.f, scopeEnd, kConst);
}

signed main() {
    cin.tie(0);
    // ios_base::sync_with_stdio(0);

    cin >> height >> width;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            char c;
            cin >> c;
            if (c == '.') grid[i][j] = -1;
            else grid[i][j] = (int)(c)-48;
        }
    }
    for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) as[i][j] = false;
    for (int i = 0; i < height; i++) for (int j = 0; j <= width; j++) countIntervals[i][j] = 0;
    for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) if (grid[i][j] != -1 and !as[i][j]) {
        mp res = dfs(i, j);
        res.f.f++;
        res.f.s++;
        countIntervals[res.f.f][res.f.f] += res.s;
        countIntervals[res.f.f][res.f.s+1] -= res.s;
    }
    width++;
    for (int i = 0; i < width; i++) for (int j = 1; j < width; j++) countIntervals[i][j] += countIntervals[i][j-1];
    for (int i = 0; i < width; i++) for (int j = 0; j < width; j++) jNotI[i][j] = 0;
    for (int j = 0; j < width; j++) {
        for (int i = j-1; i >= 0; i--) {
            jNotI[i][j] = jNotI[i+1][j]+countIntervals[i+1][j];
        }
    }
    for (int i = 0; i < width; i++) for (int j = 0; j <= width; j++) dp[i][j] = 0;
    for (int i = 1; i <= width; i++) {
        compute(0, width-1, 0, width-1, i);
    }
    for (int i = 1; i < width; i++) {
        int maxScore = 0;
        for (int j = 0; j < width; j++) maxScore = max(maxScore, dp[j][i]);
        cout << maxScore << endl;
    }

    int d = 0;
    d++;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1204 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1204 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 16 ms 8556 KB Output is correct
8 Correct 14 ms 8548 KB Output is correct
9 Correct 16 ms 10564 KB Output is correct
10 Correct 13 ms 8656 KB Output is correct
11 Correct 12 ms 8540 KB Output is correct
12 Correct 11 ms 8572 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1204 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 16 ms 8556 KB Output is correct
8 Correct 14 ms 8548 KB Output is correct
9 Correct 16 ms 10564 KB Output is correct
10 Correct 13 ms 8656 KB Output is correct
11 Correct 12 ms 8540 KB Output is correct
12 Correct 11 ms 8572 KB Output is correct
13 Correct 611 ms 133864 KB Output is correct
14 Correct 652 ms 133652 KB Output is correct
15 Correct 740 ms 212956 KB Output is correct
16 Correct 541 ms 133572 KB Output is correct
17 Correct 523 ms 133620 KB Output is correct
18 Correct 539 ms 133708 KB Output is correct