| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 428127 |
2021-06-15T08:15:43 Z |
fvogel499 |
Nafta (COI15_nafta) |
C++14 |
|
1 ms |
1228 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++;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
