QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#372087#2432. Go with the FlowUFRJ#AC ✓2227ms4016kbC++202.1kb2024-03-30 21:22:052024-03-30 21:22:06

Judging History

This is the latest submission verdict.

  • [2024-03-30 21:22:06]
  • Judged
  • Verdict: AC
  • Time: 2227ms
  • Memory: 4016kb
  • [2024-03-30 21:22:05]
  • Submitted

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 += 1 + 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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3548kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

score: 0
Accepted
time: 58ms
memory: 3616kb

Test #14:

score: 0
Accepted
time: 55ms
memory: 3944kb

Test #15:

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

Test #16:

score: 0
Accepted
time: 569ms
memory: 3772kb

Test #17:

score: 0
Accepted
time: 569ms
memory: 3744kb

Test #18:

score: 0
Accepted
time: 569ms
memory: 3724kb

Test #19:

score: 0
Accepted
time: 170ms
memory: 3796kb

Test #20:

score: 0
Accepted
time: 95ms
memory: 3756kb

Test #21:

score: 0
Accepted
time: 1224ms
memory: 3696kb

Test #22:

score: 0
Accepted
time: 2056ms
memory: 3788kb

Test #23:

score: 0
Accepted
time: 57ms
memory: 3688kb

Test #24:

score: 0
Accepted
time: 98ms
memory: 3712kb

Test #25:

score: 0
Accepted
time: 774ms
memory: 3920kb

Test #26:

score: 0
Accepted
time: 779ms
memory: 3740kb

Test #27:

score: 0
Accepted
time: 792ms
memory: 3684kb

Test #28:

score: 0
Accepted
time: 202ms
memory: 3688kb

Test #29:

score: 0
Accepted
time: 216ms
memory: 3896kb

Test #30:

score: 0
Accepted
time: 204ms
memory: 3916kb

Test #31:

score: 0
Accepted
time: 1857ms
memory: 3740kb

Test #32:

score: 0
Accepted
time: 1080ms
memory: 3996kb

Test #33:

score: 0
Accepted
time: 1208ms
memory: 3764kb

Test #34:

score: 0
Accepted
time: 53ms
memory: 3680kb

Test #35:

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

Test #36:

score: 0
Accepted
time: 1259ms
memory: 4012kb

Test #37:

score: 0
Accepted
time: 1905ms
memory: 3728kb

Test #38:

score: 0
Accepted
time: 1870ms
memory: 3764kb

Test #39:

score: 0
Accepted
time: 1610ms
memory: 3744kb

Test #40:

score: 0
Accepted
time: 1680ms
memory: 3732kb

Test #41:

score: 0
Accepted
time: 1709ms
memory: 4016kb

Test #42:

score: 0
Accepted
time: 1921ms
memory: 3756kb

Test #43:

score: 0
Accepted
time: 1978ms
memory: 3728kb

Test #44:

score: 0
Accepted
time: 1894ms
memory: 3768kb

Test #45:

score: 0
Accepted
time: 1588ms
memory: 3724kb

Test #46:

score: 0
Accepted
time: 1580ms
memory: 3812kb

Test #47:

score: 0
Accepted
time: 1608ms
memory: 3724kb

Test #48:

score: 0
Accepted
time: 1563ms
memory: 3740kb

Test #49:

score: 0
Accepted
time: 1827ms
memory: 3812kb

Test #50:

score: 0
Accepted
time: 1694ms
memory: 3708kb

Test #51:

score: 0
Accepted
time: 1607ms
memory: 3768kb

Test #52:

score: 0
Accepted
time: 1586ms
memory: 3904kb

Test #53:

score: 0
Accepted
time: 1406ms
memory: 3724kb

Test #54:

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

Test #55:

score: 0
Accepted
time: 83ms
memory: 3608kb

Test #56:

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

Test #57:

score: 0
Accepted
time: 2227ms
memory: 3744kb

Test #58:

score: 0
Accepted
time: 2208ms
memory: 3740kb

Test #59:

score: 0
Accepted
time: 95ms
memory: 3660kb

Test #60:

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

Test #61:

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

Test #62:

score: 0
Accepted
time: 42ms
memory: 3908kb

Test #63:

score: 0
Accepted
time: 250ms
memory: 3628kb

Test #64:

score: 0
Accepted
time: 112ms
memory: 3596kb

Test #65:

score: 0
Accepted
time: 1491ms
memory: 3752kb

Test #66:

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