QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521166#2432. Go with the FlowJooDdaeTL 3021ms6236kbC++201.0kb2024-08-15 22:53:422024-08-15 22:53:42

Judging History

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

  • [2024-08-15 22:53:42]
  • 评测
  • 测评结果:TL
  • 用时:3021ms
  • 内存:6236kb
  • [2024-08-15 22:53:42]
  • 提交

answer

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

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

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;
        int cnt = 0;

        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, cnt++;
        }
        if(cnt <= ans2) break;

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

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

详细

Test #1:

score: 100
Accepted
time: 13ms
memory: 6164kb

Test #2:

score: 0
Accepted
time: 11ms
memory: 6220kb

Test #3:

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

Test #4:

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

Test #5:

score: 0
Accepted
time: 50ms
memory: 6024kb

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 0
Accepted
time: 6ms
memory: 5920kb

Test #12:

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

Test #13:

score: 0
Accepted
time: 2856ms
memory: 6236kb

Test #14:

score: 0
Accepted
time: 2947ms
memory: 6032kb

Test #15:

score: 0
Accepted
time: 3021ms
memory: 6228kb

Test #16:

score: -100
Time Limit Exceeded