Submission #428158

#	Time	Username	Problem	Language	Result	Execution time	Memory
428158		fvogel499	Nafta (COI15_nafta)	C++14	100 / 100	740 ms	212956 KiB

nafta

/*
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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66