oj.uz

Submission #893295

# Submission time Handle Problem Language Result Execution time Memory
893295 2023-12-26T21:23:00 Z coloboxx Nafta (COI15_nafta) C++17
100 / 100
 191 ms 143696 KB 
// O(RS)
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int MAXN = 2020;

vector<pair<int, int>> v[MAXN];

bool bio[MAXN][MAXN];
char a[MAXN][MAXN];

int opt[MAXN][MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int cnt[MAXN];
int n, m;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int i, int j, int &l, int &r, int &s) {
  if (bio[i][j]) return;
  bio[i][j] = true;
  
  l = min(l, j);
  r = max(r, j);
  s += a[i][j] - '0';

  REP(k, 4) {
    int ni = i + dx[k];
    int nj = j + dy[k];
    if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
    if (a[ni][nj] != '.') dfs(ni, nj, l, r, s);
  }
}

int main(void) {
  int t = 1;
  while (t--) {
    scanf("%d %d", &n, &m);
    REP(i, n) scanf("%s", a[i]);

    REP(i, n) REP(j, m) bio[i][j] = false;
    REP(j, m) v[j].clear();

    REP(i, n) REP(j, m)
      if (!bio[i][j] && a[i][j] != '.') {
        int l = j, r = j, s = 0;
        dfs(i, j, l, r, s);
        v[l].push_back({r, s});
      }
    
    REP(j, m) cnt[j] = 0;
    for (int j = m-1; j >= 0; --j) {
      for (auto &p: v[j])
        FOR(i, j, p.first+1) cnt[i] += p.second;
      FOR(i, j, m) g[j][i] = cnt[i];
    }

    REP(i, m+1) {
      f[0][i] = 0;
      opt[0][i] = m-1;
    }

    for (int k = 1; k <= m; ++k) {
      int best = 0;
      for (int i = 0; i < m; ++i) {
        int lo = i == 0 ? 0 : max(i, opt[k][i-1]);
        int hi = opt[k-1][i];

        f[k][i] = -1;
        for (int j = lo; j <= hi; ++j) {
          int nf = f[k-1][j+1] + g[i][j];
          if (nf > f[k][i]) f[k][i] = nf, opt[k][i] = j;
        }

        best = max(best, f[k][i]);
      }
      printf("%d\n", best);
    }
  }
  return 0;
}

Compilation message

nafta.cpp: In function 'int main()':
nafta.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
nafta.cpp:52:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     REP(i, n) scanf("%s", a[i]);
      |               ~~~~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10740 KB Output is correct
7 Correct 4 ms 17400 KB Output is correct
8 Correct 5 ms 17140 KB Output is correct
9 Correct 7 ms 19544 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 17156 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10740 KB Output is correct
7 Correct 4 ms 17400 KB Output is correct
8 Correct 5 ms 17140 KB Output is correct
9 Correct 7 ms 19544 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 17156 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 76 ms 67204 KB Output is correct
14 Correct 116 ms 64036 KB Output is correct
15 Correct 191 ms 143696 KB Output is correct
16 Correct 61 ms 63444 KB Output is correct
17 Correct 48 ms 60316 KB Output is correct
18 Correct 46 ms 60356 KB Output is correct