oj.uz

Submission #21042

# Submission time Handle Problem Language Result Execution time Memory
21042 2017-04-03T11:15:26 Z model_code Nafta (COI15_nafta) C++11
100 / 100
 243 ms 140724 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:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
                           ^
nafta.cpp:52:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     REP(i, n) scanf("%s", a[i]);
                                ^

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 57860 KB Output is correct
2 Correct 0 ms 57860 KB Output is correct
3 Correct 0 ms 57860 KB Output is correct
4 Correct 0 ms 57860 KB Output is correct
5 Correct 0 ms 57860 KB Output is correct
6 Correct 0 ms 57860 KB Output is correct
7 Correct 3 ms 57992 KB Output is correct
8 Correct 6 ms 57992 KB Output is correct
9 Correct 0 ms 59788 KB Output is correct
10 Correct 0 ms 57992 KB Output is correct
11 Correct 0 ms 57860 KB Output is correct
12 Correct 3 ms 57860 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 57860 KB Output is correct
2 Correct 0 ms 57860 KB Output is correct
3 Correct 0 ms 57860 KB Output is correct
4 Correct 0 ms 57860 KB Output is correct
5 Correct 0 ms 57860 KB Output is correct
6 Correct 0 ms 57860 KB Output is correct
7 Correct 3 ms 57992 KB Output is correct
8 Correct 6 ms 57992 KB Output is correct
9 Correct 0 ms 59788 KB Output is correct
10 Correct 0 ms 57992 KB Output is correct
11 Correct 0 ms 57860 KB Output is correct
12 Correct 3 ms 57860 KB Output is correct
13 Correct 153 ms 64856 KB Output is correct
14 Correct 189 ms 61688 KB Output is correct
15 Correct 243 ms 140724 KB Output is correct
16 Correct 96 ms 61028 KB Output is correct
17 Correct 79 ms 58124 KB Output is correct
18 Correct 73 ms 57992 KB Output is correct