QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521165#2432. Go with the FlowJooDdaeTL 2996ms5420kbC++20965b2024-08-15 22:48:332024-08-15 22:48:33

Judging History

你现在查看的是最新测评结果

  • [2024-08-15 22:48:33]
  • 评测
  • 测评结果:TL
  • 用时:2996ms
  • 内存:5420kb
  • [2024-08-15 22:48:33]
  • 提交

answer

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

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

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++) {
        vector<int> V;

        for(int i=1;i<=n;i++) {
            int C = d[i], j = i;
            vector<int> U;
            while(j+1 <= n && C+1+d[j+1] <= L) U.push_back(++C), C += d[++j];

            for(auto C : U) {
                dp[C] = max({tmp[C-1], tmp[C], tmp[C+1]})+1;
                if(dp[C] > ans2) ans2 = dp[C], ans1 = L;
            }
            for(auto C : V) tmp[C] = 0;
            swap(dp, tmp), swap(U, V);

            i = j;
        }

        for(auto C : V) tmp[C] = 0;
    }

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

Details

Test #1:

score: 100
Accepted
time: 17ms
memory: 5408kb

Test #2:

score: 0
Accepted
time: 16ms
memory: 5384kb

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 61ms
memory: 5152kb

Test #13:

score: 0
Accepted
time: 2966ms
memory: 5232kb

Test #14:

score: 0
Accepted
time: 2958ms
memory: 5108kb

Test #15:

score: 0
Accepted
time: 2996ms
memory: 5420kb

Test #16:

score: -100
Time Limit Exceeded