QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#380765#2432. Go with the Flow8BQube#AC ✓4605ms11108kbC++201.7kb2024-04-07 11:26:592024-04-07 11:26:59

Judging History

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

  • [2024-04-07 11:26:59]
  • 评测
  • 测评结果:AC
  • 用时:4605ms
  • 内存:11108kb
  • [2024-04-07 11:26:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

int vis[1000005], dp[1000005];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<string> vec(n);
    for (auto &s : vec)
        cin >> s;

    pii ans = pii(-1, 0);

    auto check = [&](int width) {

        vector<int> arr;
        int cur = 0, cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (cur == 0 || cur + 1 + SZ(vec[i]) > width) {
                if (cur != 0) ++cnt;
                cur = SZ(vec[i]);
            }
            else {
                vis[cnt * width + cur] = width;
                arr.pb(cnt * width + cur);
                dp[cnt * width + cur] = 1;
                cur += 1 + SZ(vec[i]);
            }
        }
        ++cnt;

        auto get_val = [&](int x, int y, int &mx) {
            if (x < 0 || y < 0 || x >= cnt || y >= width || vis[x * width + y] != width) return;
            mx = max(dp[x * width + y], mx);
        };

        int nw = 0;
        for (int i : arr) {
            int x = i / width, y = i % width;
            int mx = 0;
            get_val(x - 1, y - 1, mx);
            get_val(x - 1, y, mx);
            get_val(x - 1, y + 1, mx);
            dp[i] = max(1, mx + 1);
            nw = max(nw, dp[i]);
        }
        
        if (nw > ans.X)
            ans = pii(nw, width);
    };

    int sum = SZ(vec[0]), mx = SZ(vec[0]);
    for (int i = 1; i < n; ++i)
        sum += 1 + SZ(vec[i]), mx = max(mx, SZ(vec[i]));
    for (int i = mx; i <= sum; ++i)
        check(i);

    cout << ans.Y << " " << ans.X << "\n";
}

详细

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

score: 0
Accepted
time: 68ms
memory: 5800kb

Test #14:

score: 0
Accepted
time: 64ms
memory: 5764kb

Test #15:

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

Test #16:

score: 0
Accepted
time: 865ms
memory: 5944kb

Test #17:

score: 0
Accepted
time: 843ms
memory: 8036kb

Test #18:

score: 0
Accepted
time: 765ms
memory: 7968kb

Test #19:

score: 0
Accepted
time: 200ms
memory: 6028kb

Test #20:

score: 0
Accepted
time: 131ms
memory: 5808kb

Test #21:

score: 0
Accepted
time: 2077ms
memory: 6468kb

Test #22:

score: 0
Accepted
time: 4233ms
memory: 11100kb

Test #23:

score: 0
Accepted
time: 68ms
memory: 5976kb

Test #24:

score: 0
Accepted
time: 133ms
memory: 5744kb

Test #25:

score: 0
Accepted
time: 1270ms
memory: 8260kb

Test #26:

score: 0
Accepted
time: 1282ms
memory: 6292kb

Test #27:

score: 0
Accepted
time: 1409ms
memory: 6268kb

Test #28:

score: 0
Accepted
time: 307ms
memory: 5864kb

Test #29:

score: 0
Accepted
time: 340ms
memory: 8052kb

Test #30:

score: 0
Accepted
time: 322ms
memory: 5964kb

Test #31:

score: 0
Accepted
time: 3801ms
memory: 9544kb

Test #32:

score: 0
Accepted
time: 2049ms
memory: 10240kb

Test #33:

score: 0
Accepted
time: 1663ms
memory: 6604kb

Test #34:

score: 0
Accepted
time: 66ms
memory: 5740kb

Test #35:

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

Test #36:

score: 0
Accepted
time: 2014ms
memory: 6392kb

Test #37:

score: 0
Accepted
time: 3954ms
memory: 10984kb

Test #38:

score: 0
Accepted
time: 3877ms
memory: 10992kb

Test #39:

score: 0
Accepted
time: 3189ms
memory: 6860kb

Test #40:

score: 0
Accepted
time: 3327ms
memory: 10384kb

Test #41:

score: 0
Accepted
time: 3414ms
memory: 8944kb

Test #42:

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

Test #43:

score: 0
Accepted
time: 4051ms
memory: 7360kb

Test #44:

score: 0
Accepted
time: 4255ms
memory: 10696kb

Test #45:

score: 0
Accepted
time: 3208ms
memory: 8976kb

Test #46:

score: 0
Accepted
time: 3079ms
memory: 6836kb

Test #47:

score: 0
Accepted
time: 3143ms
memory: 9092kb

Test #48:

score: 0
Accepted
time: 3054ms
memory: 6796kb

Test #49:

score: 0
Accepted
time: 3715ms
memory: 10076kb

Test #50:

score: 0
Accepted
time: 3448ms
memory: 6972kb

Test #51:

score: 0
Accepted
time: 3175ms
memory: 10312kb

Test #52:

score: 0
Accepted
time: 3437ms
memory: 6856kb

Test #53:

score: 0
Accepted
time: 2639ms
memory: 6684kb

Test #54:

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

Test #55:

score: 0
Accepted
time: 123ms
memory: 6068kb

Test #56:

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

Test #57:

score: 0
Accepted
time: 4605ms
memory: 10232kb

Test #58:

score: 0
Accepted
time: 4605ms
memory: 10920kb

Test #59:

score: 0
Accepted
time: 144ms
memory: 5964kb

Test #60:

score: 0
Accepted
time: 77ms
memory: 5788kb

Test #61:

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

Test #62:

score: 0
Accepted
time: 51ms
memory: 7852kb

Test #63:

score: 0
Accepted
time: 450ms
memory: 8360kb

Test #64:

score: 0
Accepted
time: 177ms
memory: 5968kb

Test #65:

score: 0
Accepted
time: 2844ms
memory: 6700kb

Test #66:

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