QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372084#2432. Go with the FlowUFRJ#WA 1ms3820kbC++202.1kb2024-03-30 21:17:422024-03-30 21:17:44

Judging History

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

  • [2024-03-30 21:17:44]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3820kb
  • [2024-03-30 21:17:42]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;
using lint = int64_t;

int main(void) {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin>>n;
    vector<int> v(n);
    int left = 0, right = 0;
    for(int i =0; i<n; i++){
        string s; cin>>s;
        v[i] = int(s.size());
        left = max(left, v[i]);
        right += v[i];
    }

    auto test = [&](int tam) -> int {
        vector<vector<int>> mat = {{}};
        int cur = 0;
        for(int x : v){
            if(cur == 0){
                cur = x;
                mat.back().push_back(cur);
            } else if(cur + 1 + x <= tam){
                cur += 1 + x;
                mat.back().push_back(cur);
            } else {
                mat.push_back({});
                cur = x;
                mat.back().push_back(cur);
            }
        }
        for(auto &row : mat){
            row.pop_back();
        }

        // for(int i =0; i <int(mat.size()); i++){
        //     for(int x : mat[i])
        //         cout<<x<<" ";
        //     cout<<"\n";
        // }
        // cout<<"DP\n";

        const int t = int(mat.size());
        int ans = 0;
        vector<int> dp(mat[0].size(), 1);
        for(int i = 0; i + 1 < t; i++){
            for(int d : dp){
                ans = max(ans, d);
            }
            vector<int> nxt(mat[i+1].size(), 1);
            for(int l = 0, r = 0; l < int(mat[i].size()); l++){
                int x = mat[i][l];
                while(mat[i+1][r] < (x - 1) && r < int(mat[i+1].size())) r++;
                for(int j = r; j < int(mat[i+1].size()); j++){
                    if(mat[i+1][j] > x + 1) break;
                    nxt[j] = max(nxt[j], dp[l] + 1);
                }
            }
            dp = nxt;
        }
        for(int d : dp) ans = max(ans, d);
        return ans;
    };

    pair<int, int> ans = {0, left};
    for(int tam = left; tam <= right; tam++){
        int cur = test(tam);
        if(cur > ans.first){
            ans = {cur, tam};
        }
    }
    cout<<ans.second<<" "<<ans.first<<"\n";

    return 0;
}

Details

Test #1:

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

Test #2:

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

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3588kb