QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217968#2432. Go with the FlowKronos#AC ✓895ms4300kbC++141.1kb2023-10-17 16:40:292023-10-17 16:40:30

Judging History

This is the latest submission verdict.

  • [2023-10-17 16:40:30]
  • Judged
  • Verdict: AC
  • Time: 895ms
  • Memory: 4300kb
  • [2023-10-17 16:40:29]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n; cin >> n;

  vector <string> a(n);
  int mx_len = 0, tot_len = 0;
  for (auto &s : a) cin >> s, mx_len = max(mx_len, (int) s.size()), tot_len += s.size();
  tot_len += n;

  int sz = tot_len, river = 0;

  for (int L = mx_len; L <= tot_len; ++L) {
    int cur_len = 0;
    int cur_river = 0;

    vector <int> dp[2];
    dp[0].assign(L + 1, 0);
    dp[1].assign(L + 1, 0);

    for (int i = 0; i < n;) {
      dp[L & 1].assign(L + 1, 0);
      int nxt = a[i].size();
      i += 1;
      while (i < n && nxt + 1 + a[i].size() <= L) {
        dp[L & 1][nxt] = max({dp[L & 1][nxt], 1 + dp[L & 1 ^ 1][nxt - 1], 
                      1 + dp[L & 1 ^ 1][nxt], 1 + dp[L & 1 ^ 1][nxt + 1]});
        cur_river = max(cur_river, dp[L & 1][nxt]);
        nxt += 1 + a[i].size();
        i += 1;
      }
      swap(dp[0], dp[1]);
      cur_len += 1;
    }

    if (cur_river > river) {
      river = cur_river;
      sz = L;
    }

    if (cur_len <= river) break;
  }

  cout << sz << ' ' << river << '\n';
}

Details

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 3516kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 3612kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 3552kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 3852kb

Test #6:

score: 0
Accepted
time: 0ms
memory: 3568kb

Test #7:

score: 0
Accepted
time: 0ms
memory: 3612kb

Test #8:

score: 0
Accepted
time: 0ms
memory: 3620kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 3560kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 3728kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 3648kb

Test #12:

score: 0
Accepted
time: 0ms
memory: 3616kb

Test #13:

score: 0
Accepted
time: 2ms
memory: 3720kb

Test #14:

score: 0
Accepted
time: 2ms
memory: 3668kb

Test #15:

score: 0
Accepted
time: 3ms
memory: 3668kb

Test #16:

score: 0
Accepted
time: 30ms
memory: 3860kb

Test #17:

score: 0
Accepted
time: 27ms
memory: 3792kb

Test #18:

score: 0
Accepted
time: 26ms
memory: 4020kb

Test #19:

score: 0
Accepted
time: 2ms
memory: 3768kb

Test #20:

score: 0
Accepted
time: 1ms
memory: 3696kb

Test #21:

score: 0
Accepted
time: 130ms
memory: 3936kb

Test #22:

score: 0
Accepted
time: 2ms
memory: 3836kb

Test #23:

score: 0
Accepted
time: 0ms
memory: 3640kb

Test #24:

score: 0
Accepted
time: 0ms
memory: 3692kb

Test #25:

score: 0
Accepted
time: 84ms
memory: 4168kb

Test #26:

score: 0
Accepted
time: 109ms
memory: 3928kb

Test #27:

score: 0
Accepted
time: 112ms
memory: 3896kb

Test #28:

score: 0
Accepted
time: 13ms
memory: 4036kb

Test #29:

score: 0
Accepted
time: 27ms
memory: 3796kb

Test #30:

score: 0
Accepted
time: 25ms
memory: 3792kb

Test #31:

score: 0
Accepted
time: 264ms
memory: 4276kb

Test #32:

score: 0
Accepted
time: 10ms
memory: 3872kb

Test #33:

score: 0
Accepted
time: 3ms
memory: 4068kb

Test #34:

score: 0
Accepted
time: 0ms
memory: 3700kb

Test #35:

score: 0
Accepted
time: 0ms
memory: 3708kb

Test #36:

score: 0
Accepted
time: 144ms
memory: 3892kb

Test #37:

score: 0
Accepted
time: 258ms
memory: 4052kb

Test #38:

score: 0
Accepted
time: 299ms
memory: 4052kb

Test #39:

score: 0
Accepted
time: 465ms
memory: 4268kb

Test #40:

score: 0
Accepted
time: 529ms
memory: 4060kb

Test #41:

score: 0
Accepted
time: 549ms
memory: 4080kb

Test #42:

score: 0
Accepted
time: 195ms
memory: 4300kb

Test #43:

score: 0
Accepted
time: 261ms
memory: 4124kb

Test #44:

score: 0
Accepted
time: 323ms
memory: 4144kb

Test #45:

score: 0
Accepted
time: 701ms
memory: 4072kb

Test #46:

score: 0
Accepted
time: 692ms
memory: 4072kb

Test #47:

score: 0
Accepted
time: 652ms
memory: 4076kb

Test #48:

score: 0
Accepted
time: 560ms
memory: 4044kb

Test #49:

score: 0
Accepted
time: 678ms
memory: 4076kb

Test #50:

score: 0
Accepted
time: 512ms
memory: 4064kb

Test #51:

score: 0
Accepted
time: 719ms
memory: 4076kb

Test #52:

score: 0
Accepted
time: 704ms
memory: 4116kb

Test #53:

score: 0
Accepted
time: 280ms
memory: 4284kb

Test #54:

score: 0
Accepted
time: 1ms
memory: 3924kb

Test #55:

score: 0
Accepted
time: 27ms
memory: 3744kb

Test #56:

score: 0
Accepted
time: 4ms
memory: 3728kb

Test #57:

score: 0
Accepted
time: 3ms
memory: 4224kb

Test #58:

score: 0
Accepted
time: 5ms
memory: 4196kb

Test #59:

score: 0
Accepted
time: 32ms
memory: 3816kb

Test #60:

score: 0
Accepted
time: 12ms
memory: 4012kb

Test #61:

score: 0
Accepted
time: 1ms
memory: 3696kb

Test #62:

score: 0
Accepted
time: 21ms
memory: 3952kb

Test #63:

score: 0
Accepted
time: 96ms
memory: 3904kb

Test #64:

score: 0
Accepted
time: 86ms
memory: 3844kb

Test #65:

score: 0
Accepted
time: 895ms
memory: 4100kb

Test #66:

score: 0
Accepted
time: 0ms
memory: 3616kb