QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521167#2432. Go with the FlowJooDdaeTL 5793ms8040kbC++201.0kb2024-08-15 22:57:452024-08-15 22:57:45

Judging History

This is the latest submission verdict.

  • [2024-08-15 22:57:45]
  • Judged
  • Verdict: TL
  • Time: 5793ms
  • Memory: 8040kb
  • [2024-08-15 22:57:45]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, S, d[3030], dp[300200], tmp[300200];

int q[2][300300], sz[2];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) {
        string s; cin >> s;
        d[i] = s.size(), S += d[i]+1;
    }

    int mx = *max_element(d+1, d+1+n);
    int ans1 = 0, ans2 = 0;

    for(int L=mx;L<S;L++) {
        for(int i=1, u=0;i<=n;i++, u=!u) {
            int C = d[i], j = i;
            while(j+1 <= n && C+1+d[j+1] <= L) q[u][sz[u]++] = ++C, C += d[++j];

            for(int i=0;i<sz[u];i++) {
                int C = q[u][i];
                dp[C] = max({tmp[C-1], tmp[C], tmp[C+1]})+1;
                if(dp[C] > ans2) ans2 = dp[C], ans1 = L;
            }
            for(int i=0;i<sz[!u];i++) {
                tmp[q[!u][i]] = 0;
            }
            sz[!u] = 0, i = j, swap(dp, tmp);
        }

        for(int i=0;i<2;i++) for(int j=0;j<sz[i];j++) tmp[q[i][j]] = 0;
    }

    cout << ans1 << " " << ans2 << "\n";
}

Details

Test #1:

score: 100
Accepted
time: 33ms
memory: 6040kb

Test #2:

score: 0
Accepted
time: 38ms
memory: 5884kb

Test #3:

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

Test #4:

score: 0
Accepted
time: 63ms
memory: 6232kb

Test #5:

score: 0
Accepted
time: 256ms
memory: 5932kb

Test #6:

score: 0
Accepted
time: 278ms
memory: 6200kb

Test #7:

score: 0
Accepted
time: 51ms
memory: 6000kb

Test #8:

score: 0
Accepted
time: 60ms
memory: 6060kb

Test #9:

score: 0
Accepted
time: 56ms
memory: 6000kb

Test #10:

score: 0
Accepted
time: 49ms
memory: 5996kb

Test #11:

score: 0
Accepted
time: 52ms
memory: 8040kb

Test #12:

score: 0
Accepted
time: 128ms
memory: 6200kb

Test #13:

score: 0
Accepted
time: 5627ms
memory: 5980kb

Test #14:

score: 0
Accepted
time: 5673ms
memory: 5948kb

Test #15:

score: 0
Accepted
time: 5793ms
memory: 6240kb

Test #16:

score: -100
Time Limit Exceeded