QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#465512 | #7963. 多折较差验证 | propane | AC ✓ | 614ms | 394800kb | C++20 | 3.9kb | 2024-07-06 23:39:52 | 2024-07-06 23:39:55 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<random>
#include<chrono>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const int maxn = 5005;
static const ULL mod = (1ull << 61) - 1;
ULL power[maxn];
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ULL> dist(mod / 2, mod - 1);
const ULL base = dist(rnd);
static inline ULL add(ULL a, ULL b){
a += b;
if (a >= mod) a -= mod;
return a;
}
static inline ULL mul(ULL a, ULL b){
__uint128_t c = __uint128_t(a) * b;
return add(c >> 61, c & mod);
}
ULL merge(ULL h1, ULL h2, int len2){
return add(mul(h1, power[len2]), h2);
}
void init(){
power[0] = 1;
for(int i = 1; i < maxn; i++)
power[i] = mul(power[i - 1], base);
}
ULL query(const vector<ULL> &s, int l, int r){
return add(s[r], mod - mul(s[l - 1], power[r - l + 1]));
}
vector<ULL> build(const string &s){
int sz = s.size();
vector<ULL> hashed(sz + 1);
for (int i = 0; i < sz; i++){
hashed[i + 1] = add(mul(hashed[i], base), s[i]);
}
return hashed;
}
template <typename T>
vector<ULL> build(const vector<T> &s){
int sz = s.size();
vector<ULL> hashed(sz + 1);
for (int i = 0; i < sz; i++){
hashed[i + 1] = add(mul(hashed[i], base), s[i]);
}
return hashed;
}
int lcp(const vector<ULL> &a, int l1, int r1, const vector<ULL> &b, int l2, int r2){
int len = min(r1 - l1 + 1, r2 - l2 + 1);
int l = 0, r = len;
while(l < r){
int mid = (l + r + 1) / 2;
if (query(a, l1, l1 + mid - 1) == query(b, l2, l2 + mid - 1)) l = mid;
else r = mid - 1;
}
return r;
}
pair<int, int> operator+(pair<int, int> a, pair<int, int> b){
return {a.first + b.first, a.second + b.second};
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
init();
int n;
cin >> n;
string s;
cin >> s;
auto hsh1 = build(s);
reverse(s.begin(), s.end());
for(auto &c : s){
if (c == 'v') c = '^';
else c = 'v';
}
auto hsh2 = build(s);
vector<vector<pair<int, int> > > dp(n + 1, vector<pair<int, int> >(n + 1));
for(int i = 1; i <= n; i++){
dp[i][i] = {1, 0};
}
vector<vector<int> > pos1(n + 1, vector<int>(n + 1));
vector<vector<int> > pos2(n + 1, vector<int>(n + 1));
for(int i = 1; i <= n; i++){
pos1[i][i] = i;
for(int j = 2; j <= n; j++){
pos1[i][j] = pos1[i][j - 1];
if ((j - i + 1) % 2 == 1){
int mid = (i + j) / 2;
if (query(hsh1, i, mid - 1) == query(hsh2, n - j + 1, n - mid)){
pos1[i][j] = mid;
}
}
}
}
for(int i = n; i >= 1; i--){
pos2[i][i] = i;
for(int j = i - 1; j >= 1; j--){
pos2[j][i] = pos2[j + 1][i];
if ((i - j + 1) % 2 == 1){
int mid = (i + j) / 2;
if (query(hsh1, j, mid - 1) == query(hsh2, n - i + 1, n - mid)){
pos2[j][i] = mid;
}
}
}
}
for(int len = 2; len <= n; len++){
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
{
int pos = pos1[l][r];
dp[l][r] = dp[pos + 1][r] + pair(1, ((r - pos) - (pos - l)));
}
{
int pos = pos2[l][r];
dp[l][r] = min(dp[l][r], dp[l][pos - 1] + pair(1, ((pos - l) - (r - pos))));
}
// cout << pos1[l][r] << ' ' << pos2[l][r] << '\n';
// cout << l << ' ' << r << ' ' << dp[l][r].first << '\n';
}
}
cout << dp[1][n].first << ' ' << dp[1][n].second << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 510ms
memory: 394660kb
input:
5000 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...
output:
5000 12497500
result:
ok single line: '5000 12497500'
Test #2:
score: 0
Accepted
time: 534ms
memory: 393352kb
input:
4991 ^^vv^v^^^^vvv^^^^^^vvvv^^^^^^^vv^^^^^^^^v^^^^^^v^^^v^^v^^^v^^^^^v^^v^^^^^^^^vv^^^^^^^^^^vvvvvvv^v^^^^^v^v^^^^^v^^^^^^^^^^^v^^^^^vv^v^^^^^v^^^^vvv^^^v^^^^v^^^^^vv^^v^^^^^^^v^^^^^^^^^v^v^^^v^^v^^^^^v^^^vv^v^^^v^^^v^v^v^^^^v^^^vv^^^^vv^^v^^v^^^^^^^v^^^^^^v^^^^v^^^^^^v^^v^v^^^^^^^^v^^^^^v^^^v^v^^^^...
output:
2748 6735487
result:
ok single line: '2748 6735487'
Test #3:
score: 0
Accepted
time: 521ms
memory: 394656kb
input:
5000 vvvvvv^v^vvvv^^^vv^^v^v^^^vvvv^v^v^v^v^v^v^vvvvvvvv^^vvv^vvvvvvvvvvvv^vvvv^^^^vvvv^vv^^vv^vvv^vvvvvvvv^^vv^^vv^vvvvv^vvv^vvvvvvvvv^v^^vv^v^vvvvv^v^v^vvvv^vvv^vvv^^vvvvv^^vvvvvvv^v^vvvvv^v^^^^v^vvv^v^vv^vvvvv^vv^vvvvvv^vvvvvv^vvvvvv^vvv^^vvvvvvv^^^^vv^vv^v^vvvv^vv^vvv^vvv^vvv^vvvvv^^^^vvvv^vvvvv...
output:
2793 6922268
result:
ok single line: '2793 6922268'
Test #4:
score: 0
Accepted
time: 534ms
memory: 394056kb
input:
4996 vv^^vvvv^^v^^^vvvv^vv^vvvvv^vv^^^vvvv^vv^^^vvv^^v^vvvvv^vvv^v^^vv^^vv^vvvvv^v^vvvvvv^^vv^v^vvv^^vv^vvvvvv^vvvv^vvvvvvvvvvvvv^vvvvv^vvv^vvv^vvv^^vv^vv^vvvvvvv^^vvv^vv^vvvv^vvvvvv^vv^vvvv^v^vvv^v^^vvv^vvvv^^vvvvvvvvvvv^^vv^v^vv^vv^vv^^v^v^^^^vvvvvv^^vvvv^vvv^vvv^v^vv^vvvvvvvv^vvv^v^^vv^vvv^vv^v^v...
output:
2784 6803847
result:
ok single line: '2784 6803847'
Test #5:
score: 0
Accepted
time: 525ms
memory: 394648kb
input:
5000 vvvvvvvvvvvvvvvvvvvvv^^vvvvvvvv^vvvvvvvvvvv^vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv^v^vvvv^vv^vvvv^vvvvvvvvvvvvvvvvvvvvvv^vv^vvvvvvvvvvvvvvvvvvvvvvvvvvvv^^vvvvvvvvvvvvvv^vvvvvvvv^vvvvvvvvvvvvvvvvv^vvv^vvvv^vvvvvvvvvvvvvvv^v^vvvvv^vvvvvv^vv^vvvvvvvvvvv^vv^vvvvvvvvvvvvv^vvvvvvvvvvvvv^vvvvvvvvvvvvv^vvvv...
output:
4052 10043778
result:
ok single line: '4052 10043778'
Test #6:
score: 0
Accepted
time: 545ms
memory: 393412kb
input:
4992 vvvvvvvvvv^vvvvvvvvvvvvvvvvvvv^vvvvvvvvvvvvvvvvv^vvv^vvv^vvv^vvvvvv^vvvvvvvv^v^vvvvvvvvvvvvvvv^vvvvvv^vvvv^vvvvvvvvvvv^v^^vvvvvvvvvvvvvvvvvvvvv^^vvvvvvvvvvvv^vv^vvvvvv^vvvvvvvvvvv^vvvvvvvvvvvvvvvvvvvvvvvvvvvv^vvv^v^vvvv^vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv^vvvvvv^v^vvvvvvvvv^vvvvvvvvv...
output:
4094 10183595
result:
ok single line: '4094 10183595'
Test #7:
score: 0
Accepted
time: 517ms
memory: 393408kb
input:
4992 ^^^^vvvvvvvvvv^^^^^vv^^^^^^^^^^vvv^^^^^^vvvvvvv^^^vv^vvvvvvvvv^vvvvvvvvv^^^^^^^^^vvvvvvvvvv^^v^vvvvvvv^^^vvvvvvvvv^^^^^^^^^^vvvvvvv^^^^^vvvvvvvvv^^^^^^^^vvvv^vvvvvvvv^^^^^^^^^^vvv^^^^^^^vvvv^^^^^^^^^vvvvvvv^^^^^^^^vvvv^^^^^vvvvvvv^^^^^^^^vvvvvvvvvv^^^vvvvvvv^^^v^^^^^^^^^vvvvvvvv^^^^^vvv^^^^^^^^...
output:
1513 3793047
result:
ok single line: '1513 3793047'
Test #8:
score: 0
Accepted
time: 519ms
memory: 394732kb
input:
4999 vvvvvvv^^^^vv^^^^^^^^^^vvvvvvvvv^^^^^^^^^^v^^^^^^^^^vvvv^vvvvv^^^^^^^^^vvvvv^vvv^^^^^^^^vvvvv^^^^^^^vvvvvvvvv^^^vvvv^^^^^^^^^^vvvvvv^^^^^vvvv^^^^^^vvvvvvvvv^^^^^^v^^^^vvvv^^^^^^^^^vvvv^^^^vvvvvvv^^^^vvvv^^^^^^^^vvvvvvvv^^^^^^^vvvvvvvv^^^^^^vvvvvvvvvv^^^^^vvvv^^^^^vv^^^^^^vvvvvvvvv^^vvvv^^vvvvvv...
output:
1641 3991610
result:
ok single line: '1641 3991610'
Test #9:
score: 0
Accepted
time: 526ms
memory: 394092kb
input:
4997 vvvvv^^^^vv^^^vv^^vvvv^^^^^vvvvvvvvvv^^^^^^^^^vvvv^^^^^^^^^vvvv^vvvvv^vvvvvvvvvv^^^^^vvv^^^^^^^^vvvv^^^^vvvvvvvvv^^^^^^vv^^^^^^^^^vv^^^^^^^vvvvvvvvv^^^^^^vvvvvvv^^^^^^^vvvvvvvvv^^^^^^^^vvvvvvv^^^^^^^^^^vvvv^^^v^^^^^vvvvv^^^^vvvvvv^^^^^^^^^vvvvvvv^^^^^vvvvvvv^^^^^^^v^^^^^^^^^vvvvvvvv^^^^vvv^vvvv...
output:
1572 3933114
result:
ok single line: '1572 3933114'
Test #10:
score: 0
Accepted
time: 531ms
memory: 394740kb
input:
4999 ^v^^^^^^^vvvvvv^^^^^^^^^^vvvvvv^^^^vvvv^^vvv^^^^^^^^^vvvvv^vvvvvvvvv^^vvv^^^^v^^^^^^^^^^vv^^^^^^^^^v^^^^^^vvvvvvvv^^^^^vv^^^^^^^^^vvvvvvvvvv^^^^^vv^^^^vvvvvvv^^^^^^^^^^vvvvvvv^^^^^^vvvvvvvv^^^vvvv^^^^^^vvvvvv^^^^vvvvvv^^^^^^v^^vvvvvvv^^^^vv^^vvvvv^^^vvvv^^^^vvvv^^^vvvvvvvvvv^^^^^^^^^vvvvv^^^^v^...
output:
1485 3659494
result:
ok single line: '1485 3659494'
Test #11:
score: 0
Accepted
time: 614ms
memory: 394680kb
input:
5000 v^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^...
output:
13 2184
result:
ok single line: '13 2184'
Test #12:
score: 0
Accepted
time: 524ms
memory: 394620kb
input:
5000 vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...
output:
5000 12497500
result:
ok single line: '5000 12497500'
Test #13:
score: 0
Accepted
time: 597ms
memory: 394724kb
input:
5000 v^^vv^vv^^^v^^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^v^^vvv^^vv^v...
output:
13 2580
result:
ok single line: '13 2580'
Test #14:
score: 0
Accepted
time: 374ms
memory: 266104kb
input:
4095 vv^vv^^vvv^^v^^^vv^vv^^^vv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^vvv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^vvv^^v^^vvv^vv^^^vv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^^vv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^^vv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^vvv^^v^^vvv^vv^^^vv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^^vv^^v^^^vv^vv^^...
output:
12 0
result:
ok single line: '12 0'
Test #15:
score: 0
Accepted
time: 362ms
memory: 266032kb
input:
4095 v^^vvv^^v^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^^v^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^^v^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^...
output:
12 0
result:
ok single line: '12 0'
Test #16:
score: 0
Accepted
time: 598ms
memory: 393952kb
input:
4994 ^vv^^^vvv^vv^vv^^v^^^^vvv^vv^^v^^v^^^vvv^^v^^v^^vvvv^^^vv^vv^vv^^^vvv^vv^vv^^v^^^vvvv^vv^^v^^v^^^vvv^^v^^v^^vv^vv^^^vvv^vv^vv^^v^^^^vvv^vv^^v^^v^^^vvv^^v^^v^^vvvv^vvvvvvv^vv^^vvv^^v^^^^^^^v^^^^vv^vv^vv^^^vvv^vv^vv^^v^^^vvvv^vv^^v^^v^^^vvv^^v^^vv^vv^vv^^^vvv^vv^vv^^v^^^^vvv^vv^^v^^v^^^vvv^^v^^v^...
output:
27 2053
result:
ok single line: '27 2053'
Test #17:
score: 0
Accepted
time: 584ms
memory: 393480kb
input:
4992 v^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^^v^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^^v^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^...
output:
14 2351
result:
ok single line: '14 2351'
Test #18:
score: 0
Accepted
time: 602ms
memory: 394144kb
input:
4997 ^^v^^^v^^^^^^vvv^^^vv^^^vv^^v^^vv^^vvv^^vvv^^^^vvv^^^vv^^^vv^^vv^vv^^vvv^^vvv^^^vvvvv^^^^vvv^^^vv^^^vv^^v^^vv^^vvv^^vvv^^^vvvv^^^vv^^^vv^^vv^vv^^vvv^^vvv^^^vvvvv^^^^vvv^^^vv^^^vv^^v^^vv^^vvv^^vvv^^^^vvv^^^vv^^^vv^^vv^vv^^vvv^^vvv^^^vvvv^^^^^vvv^^^vv^^^vv^^v^^vv^^vvv^^vvv^^^vvvv^^^vv^^^vv^^vv^vv...
output:
28 671
result:
ok single line: '28 671'
Test #19:
score: 0
Accepted
time: 590ms
memory: 394740kb
input:
4999 ^v^^^v^^^^v^v^^v^v^vvvv^vvv^v^vv^^^v^v^^^v^^^vvvv^vvv^v^vvv^^v^v^^^v^^^^v^v^^^vv^^v^^vvv^v^vvvv^vvv^v^vv^^^v^v^^^v^^^^vvv^vvv^v^vvv^^v^v^^^v^^^^v^v^vv^v^vvvv^vvv^v^vv^^^v^v^^^v^^^vvvv^vvv^v^vvv^^v^v^^^v^^^^v^v^^^vvvv^v^vvvv^vvv^v^vv^^^v^v^^^v^^^^vvv^vvv^v^vvv^^v^v^^^v^^^^v^v^^v^v^vvvv^vvv^v^vv^...
output:
35 2652
result:
ok single line: '35 2652'
Test #20:
score: 0
Accepted
time: 598ms
memory: 394664kb
input:
4999 ^v^^v^^vvv^^^^^^^^vvvvvvv^^^v^^vvv^^^^^^^vvvvvvvv^^^v^^vvv^^^^^^^^vvvvvvv^^^vv^vvv^^^^^^^vvvvvvvv^^^v^^vvv^^^^^^^^vvvvvvv^^^v^^vvv^^^^^^^vvvvvvvv^^^vv^vvv^^^^^^^^vvvvvvv^^^vv^vvv^^^^^^^vvvvvvvv^^^v^^vvv^^^^^^^^vvvvvvv^^^v^^vvv^^^^^^^vvvvvvvv^^^v^^vvv^^^^^^^^vvvvvvv^^^vv^vvv^^^^^^^vvvvvvvv^^^vv^...
output:
29 5816
result:
ok single line: '29 5816'
Test #21:
score: 0
Accepted
time: 604ms
memory: 394724kb
input:
4999 ^^^vv^vv^^^vv^vvv^^v^^vvvv^^^vv^vv^^^^^vv^^^vvvvv^^v^^vvv^^^^vv^vv^^^v^^vvv^^v^^vvvv^^^vv^vv^^^v^vv^vvv^^v^^vvv^^^^vv^vv^^^vv^vvv^^v^^vvvv^^^vv^vv^^^^^vvv^^vvvvv^^v^^vvv^^^^vv^vv^^^v^^vvv^^v^^vvvv^^^vv^vv^^vv^vv^^^v^^vv^^v^^vvv^^^^vv^vv^^^vv^vvv^^v^^vvvv^^^vv^vv^^^^^vv^^^vvvvv^^v^^vvv^^^^vv^vv^...
output:
21 1650
result:
ok single line: '21 1650'
Test #22:
score: 0
Accepted
time: 585ms
memory: 393352kb
input:
4991 ^^vv^vv^^^vv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^^vv^^v^^^vv^vv...
output:
13 2490
result:
ok single line: '13 2490'
Test #23:
score: 0
Accepted
time: 503ms
memory: 394648kb
input:
5000 ^^^v^v^vv^^vv^^v^v^vvvv^^^vv^^vvvvvv^vvvvvvvvvvvv^vvvvvv^^^^v^vv^vvv^^v^^^^v^vvvvvvv^^v^vv^^vvvvvv^vv^^v^^^^^v^^vv^vvvv^^vvv^^^vvvvv^v^vv^^vvv^v^v^vvvv^vvv^^^vv^v^vvv^^^v^^vv^vv^^v^^^^vvvv^vvv^^vv^vv^v^v^vvv^vvv^^^v^vv^^v^^vv^vvv^^v^^vvv^vvv^vv^^v^v^vvv^^^^vv^v^vvvvv^vvv^^vvvvv^v^^vv^^^^^^^v^^v...
output:
2264 5574395
result:
ok single line: '2264 5574395'
Test #24:
score: 0
Accepted
time: 601ms
memory: 394120kb
input:
4996 v^^^v^^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^...
output:
13 2218
result:
ok single line: '13 2218'
Test #25:
score: 0
Accepted
time: 592ms
memory: 393828kb
input:
4995 vvv^^vv^vv^^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vv^^^v^^vvv^^vv^vvv^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vvv^^v^^vv^^^vv^vv^^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vvv^^v^^vv^^^vv^vv^^^v^^vvv^^vv^vvv^^v^^vvv^^vv^vv^^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vv^^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vvv^^v^^vv^^^vv...
output:
13 2575
result:
ok single line: '13 2575'
Test #26:
score: 0
Accepted
time: 589ms
memory: 394684kb
input:
4999 vvv^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vv^^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vv^^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vv^^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vv^^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vv^^^v^...
output:
13 1662
result:
ok single line: '13 1662'
Test #27:
score: 0
Accepted
time: 602ms
memory: 394212kb
input:
4996 vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^v^^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^v^^vvv^^v^^vv^^^vv^vvv^^vv^vv^^^vv^vvv^^v^^vv^^^v^...
output:
13 2457
result:
ok single line: '13 2457'
Test #28:
score: 0
Accepted
time: 585ms
memory: 394096kb
input:
4997 vv^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^^v^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^vv^^vvv^^v^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^^v^^^vv^^v^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^vv^^^vv^^v^^vvv^^v^^^vv^vv^^vvv^vv^^^vv^^v^^vvv^vv^^^vv^vv^^vvv^^v^^^vv...
output:
13 2235
result:
ok single line: '13 2235'
Test #29:
score: 0
Accepted
time: 591ms
memory: 393264kb
input:
4991 ^vv^^^vv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^^vv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^vvv^^v^^^vv^vv^^vvv^^v^^vvv^vv^^^vv^^v^^^vv^vv^^^v...
output:
13 1932
result:
ok single line: '13 1932'
Test #30:
score: 0
Accepted
time: 586ms
memory: 393356kb
input:
4991 v^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vv^^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vv^^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vv^^^v^^vvv^^vv^vvv^^v^^vv^^^vv^vvv^^v^^vvv^^vv^vv^^^v^^vv^^^vv^vvv^^v^^v...
output:
13 2369
result:
ok single line: '13 2369'
Test #31:
score: 0
Accepted
time: 519ms
memory: 394672kb
input:
5000 ^vvvvvvv^^vvv^^^v^^v^vvv^v^^^vv^^vvvvvv^^^vvv^^^v^^vvv^^^v^v^v^vv^v^^v^v^v^^v^^^vv^vvv^^^v^vvvvv^v^vvvvvvvvv^^^^v^vv^^vvv^v^vvvv^v^vv^^^^^^vv^^^^^^vv^vv^v^^^v^v^^^^^v^^v^^^^^vvvvv^vvv^v^^vv^v^^vvvvv^^^^vv^vvv^^v^v^^vv^vv^^^^v^vv^^v^^^v^^^^^^^v^v^vv^^^v^^^v^^vv^^^v^^^^^v^^^v^^vvvvv^v^^^v^vvv^v^v...
output:
2188 5310449
result:
ok single line: '2188 5310449'
Test #32:
score: 0
Accepted
time: 517ms
memory: 394620kb
input:
5000 ^vv^^^^^^vv^vv^v^^vv^^^vv^v^v^^^^^^^^v^^vvv^v^^^^v^v^^^^^^^v^^^vv^^vvv^v^^^^vv^^vvvv^v^^^^^vvvvvv^vv^^^v^vvvvv^vvv^^^^v^vvvv^^^^^^^v^vvvvvv^v^^^^^vvvvv^v^^^^v^^^v^vv^vv^vvv^v^^^v^vv^v^^v^^v^vv^vvvv^^^vv^vvv^^^^vv^^^vv^v^v^v^vvvv^^^vv^^^vvvvvvv^v^vvvv^^^vv^v^^v^v^vvv^vvv^vvvvvv^v^^vvvvv^^vv^vv^v...
output:
2146 5271567
result:
ok single line: '2146 5271567'
Test #33:
score: 0
Accepted
time: 515ms
memory: 394800kb
input:
5000 ^v^v^v^vvvvvvvv^^v^v^^vv^^v^^^v^v^^^v^v^^vvvvv^vvv^^^^v^^^vvvvv^^v^v^v^^^v^v^^vv^^v^^^^v^v^vv^v^^v^^v^^vv^^vv^^^vvvv^v^vvv^^vv^v^^^^^vvvv^v^^^vv^vv^vvv^v^^vv^v^^^v^v^^^^vv^v^^^v^^^vv^vvv^^^v^vvvv^^v^^^^v^vv^v^v^^^vvvv^v^^^v^^^vv^^v^v^^^vv^v^^v^^^v^v^vvvv^vvvvv^v^vv^^^v^^v^^^^^v^v^^^^v^v^^v^^v^^...
output:
2213 5408180
result:
ok single line: '2213 5408180'
Test #34:
score: 0
Accepted
time: 513ms
memory: 394684kb
input:
5000 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^v^^^^^^^^v^^^^^^v^^^^^^^^^^^v^^^^^^^^^^^^^^^^^^^^^^^^^^v^^^^^^^^v^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^v^^v^^^^^^vv^^^^^^^v^^^^^^^^^v^^^^^v^v^^^^^^^^^^^^v^^^^^^^^^^^^v^^v^^^^^^v^^^^^^^^^^^^^^^v^^^v^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^v^^^^^^^v^^^^^^^^^^^^^^^v^^^^^^...
output:
4115 10169791
result:
ok single line: '4115 10169791'
Test #35:
score: 0
Accepted
time: 514ms
memory: 393812kb
input:
4995 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^v^^v^^^^^^^^v^^v^^^^^^^^^^^^^^^^^^^v^v^^^^^^^^^^v^^^^^^^^^v^^v^^v^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^v^v^^^^^v^^^^^^^^v^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^v^^^^^^^v^^^v^^^^^^^^^^^^v^^^^^v^^^^^^^^^^^^^^^^^^^v^^^^^^^^^^^^^^...
output:
4082 10186253
result:
ok single line: '4082 10186253'
Test #36:
score: 0
Accepted
time: 516ms
memory: 394616kb
input:
5000 ^^^v^^^^v^v^^v^^^^vvv^^^vv^^v^^^^vv^^^^^^^^v^v^^^^^^v^^v^v^v^v^^vv^^v^^^^v^^^^^^^v^v^v^^^^^^^^v^v^^^^^^^v^^v^v^^^^v^^^^^v^^^^^^vvv^^v^vv^^vvv^v^vvv^^^vvv^^^v^^^^^vv^^^^^v^v^v^^^^^^v^v^^^vv^^^^^^^^vv^^vv^v^^v^^v^v^^^^^^^^^^^^v^^v^v^^v^^^^^^vvv^^^^^^^^^^vv^v^^vv^v^vv^^v^^v^^^^^^^v^^vv^v^^^^vv^^vv...
output:
2753 6808711
result:
ok single line: '2753 6808711'