oj.uz

Submission #848623

# Submission time Handle Problem Language Result Execution time Memory
848623 2023-09-13T06:08:42 Z rxlfd314 Soccer Stadium (IOI23_soccer) C++17
0 / 100
 4500 ms 491444 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

#define vt vector

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)

int biggest_stadium(int N, vt<vt<int>> F) {
  int dp[N][N][N] = {}, psum[N], ret = 1;
  
  auto good = [&](int l, int r) {
    return psum[r] - (l ? psum[l-1] : 0) < 1;
  };
  
  auto insert = [&](int p, int v, multiset<ari2> &m) {
    auto it = m.insert({p, v});
    if (it != begin(m) && (*prev(it))[1] >= v)
      m.erase(it);
    else
      while (next(it) != end(m) && (*next(it))[1] <= v)
        m.erase(next(it));
  };
  
  FOR(row, 0, N-1) {
    FOR(i, 0, N-1)
      psum[i] = F[row][i] + (i ? psum[i-1] : 0);
    
    multiset<ari2> best; // r2, value
    ROF(l, N-1, 0) {
      FOR(r, l, N-1) {
        if (row)
          insert(r, dp[row-1][l][r], best);
        
        if (!good(l, r))
          continue;
        
        auto it = best.lower_bound({r+1, 0});
        int &ans = dp[row][l][r];
        if (it != begin(best)) {
          it--;
          ans = (*it)[1];
        }
        
        ans += r - l + 1;
        chmax(ret, ans);
      }
    }
  }
  
  int dp2[N][N][N] = {};
  ROF(row, N-1, 0) {
    FOR(i, 0, N-1)
      psum[i] = F[row][i] + (i ? psum[i-1] : 0);
    
    multiset<ari2> best, best2; // r2, value
    ROF(l, N-1, 0) {
      FOR(r, l, N-1) {
        if (row + 1 < N)
          insert(r, dp2[row+1][l][r], best);
        if (row)
          insert(r, dp[row-1][l][r], best2);
        if (!good(l, r))
          continue;
        
        auto it = best.lower_bound({r+1, 0});
        int &ans = dp2[row][l][r];
        if (it != begin(best)) {
          it--;
          ans = (*it)[1];
        }
        ans += r - l + 1;
        
        it = best2.lower_bound({r+1, 0});
        if (it != begin(best2)) {
          it--;
          chmax(ret, ans + (*it)[1]);
        }
        
        chmax(ret, ans);
      }
    }
  }
  
  return ret;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 187 ms 8272 KB ok
8 Execution timed out 4531 ms 491444 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Incorrect 0 ms 348 KB wrong
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Incorrect 0 ms 348 KB wrong
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Incorrect 0 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Incorrect 0 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 187 ms 8272 KB ok
9 Execution timed out 4531 ms 491444 KB Time limit exceeded
10 Halted 0 ms 0 KB -