QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521164#2432. Go with the FlowJooDdaeTL 3160ms5464kbC++20963b2024-08-15 22:46:572024-08-15 22:46:58

Judging History

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

  • [2024-08-15 22:46:58]
  • 评测
  • 测评结果:TL
  • 用时:3160ms
  • 内存:5464kb
  • [2024-08-15 22:46:57]
  • 提交

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;
        memset(tmp, 0, sizeof tmp);

        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;
        }
    }

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

详细

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

score: 0
Accepted
time: 159ms
memory: 5244kb

Test #7:

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

Test #8:

score: 0
Accepted
time: 34ms
memory: 5368kb

Test #9:

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

Test #10:

score: 0
Accepted
time: 31ms
memory: 5100kb

Test #11:

score: 0
Accepted
time: 31ms
memory: 5244kb

Test #12:

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

Test #13:

score: 0
Accepted
time: 3103ms
memory: 5464kb

Test #14:

score: 0
Accepted
time: 3100ms
memory: 5156kb

Test #15:

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

Test #16:

score: -100
Time Limit Exceeded