QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#357010#2432. Go with the FlowSorting#AC ✓4513ms3940kbC++201.8kb2024-03-18 17:26:292024-03-18 17:26:30

Judging History

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

  • [2024-03-18 17:26:30]
  • 评测
  • 测评结果:AC
  • 用时:4513ms
  • 内存:3940kb
  • [2024-03-18 17:26:29]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <set>
#include <map>
#include <array>

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()

const int N = 2500 + 3;

int n;
vector<int> lens;

int river(int w){
    // cout << "river " << w << endl;
    int i = 0;
    int ans = 0;
    vector<pair<int, int>> prev;

    while(i < n){
        int sum = 0;
        vector<pair<int, int>> curr;
        for(; i < n; ++i){
            sum += lens[i];
            if(sum > w){
                sum -= lens[i];
                break;
            }
            curr.push_back({sum, 1});
            sum += 1;
        }
        curr.pop_back();

        int ptr = 0;
        for(int j = 0; j < curr.size(); ++j){
            while(ptr < prev.size() && prev[ptr].first < curr[j].first - 1){
                ++ptr;
            }
            for(int j2 = ptr; j2 < min(ptr + 3, (int)prev.size()); ++j2){
                if(abs(curr[j].first - prev[j2].first) <= 1){
                    curr[j].second = max(curr[j].second, prev[j2].second + 1);
                }
            }
            ans = max(ans, curr[j].second);
        }
        swap(curr, prev);
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; ++i){
        string s;
        cin >> s;
        lens.push_back(s.size());
    }

    int l = *max_element(lens.begin(), lens.end());
    int r = accumulate(all(lens), 0) + n - 1;

    int ans = 0, ans_idx = -1;
    for(int i = l; i <= r; ++i){
        int cand = river(i);
        if(cand > ans){
            ans = cand;
            ans_idx = i;
        }
    }

    cout << ans_idx << " " << ans << "\n";
}

詳細信息

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

score: 0
Accepted
time: 92ms
memory: 3840kb

Test #14:

score: 0
Accepted
time: 90ms
memory: 3816kb

Test #15:

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

Test #16:

score: 0
Accepted
time: 1030ms
memory: 3612kb

Test #17:

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

Test #18:

score: 0
Accepted
time: 1005ms
memory: 3640kb

Test #19:

score: 0
Accepted
time: 269ms
memory: 3640kb

Test #20:

score: 0
Accepted
time: 153ms
memory: 3640kb

Test #21:

score: 0
Accepted
time: 2445ms
memory: 3640kb

Test #22:

score: 0
Accepted
time: 4513ms
memory: 3644kb

Test #23:

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

Test #24:

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

Test #25:

score: 0
Accepted
time: 1524ms
memory: 3612kb

Test #26:

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

Test #27:

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

Test #28:

score: 0
Accepted
time: 379ms
memory: 3644kb

Test #29:

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

Test #30:

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

Test #31:

score: 0
Accepted
time: 4103ms
memory: 3864kb

Test #32:

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

Test #33:

score: 0
Accepted
time: 2372ms
memory: 3864kb

Test #34:

score: 0
Accepted
time: 104ms
memory: 3632kb

Test #35:

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

Test #36:

score: 0
Accepted
time: 2402ms
memory: 3864kb

Test #37:

score: 0
Accepted
time: 4224ms
memory: 3868kb

Test #38:

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

Test #39:

score: 0
Accepted
time: 3466ms
memory: 3656kb

Test #40:

score: 0
Accepted
time: 3631ms
memory: 3940kb

Test #41:

score: 0
Accepted
time: 3718ms
memory: 3648kb

Test #42:

score: 0
Accepted
time: 4215ms
memory: 3640kb

Test #43:

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

Test #44:

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

Test #45:

score: 0
Accepted
time: 3454ms
memory: 3704kb

Test #46:

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

Test #47:

score: 0
Accepted
time: 3452ms
memory: 3900kb

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

score: 0
Accepted
time: 3497ms
memory: 3644kb

Test #52:

score: 0
Accepted
time: 3461ms
memory: 3644kb

Test #53:

score: 0
Accepted
time: 2955ms
memory: 3932kb

Test #54:

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

Test #55:

score: 0
Accepted
time: 150ms
memory: 3884kb

Test #56:

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

Test #57:

score: 0
Accepted
time: 4470ms
memory: 3636kb

Test #58:

score: 0
Accepted
time: 4490ms
memory: 3640kb

Test #59:

score: 0
Accepted
time: 175ms
memory: 3656kb

Test #60:

score: 0
Accepted
time: 97ms
memory: 3804kb

Test #61:

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

Test #62:

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

Test #63:

score: 0
Accepted
time: 490ms
memory: 3568kb

Test #64:

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

Test #65:

score: 0
Accepted
time: 3168ms
memory: 3636kb

Test #66:

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