QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22486#2356. Partition of Queriesli0201#AC ✓43ms47740kbC++201.8kb2022-03-09 19:04:372022-04-30 01:11:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:11:54]
  • 评测
  • 测评结果:AC
  • 用时:43ms
  • 内存:47740kb
  • [2022-03-09 19:04:37]
  • 提交

answer

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)

inline int read() {
    int f = 1, x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

const int N = 1e6 + 7;
using namespace std;
int n;
ll f[N], g[N], W;
char ch[N];
ll w[N], s[N], c[N];
int q[N], hd, tl;
ll X(int i) { return w[i]; }
ll Y(int i) { return g[i]; }
double slope(int i, int j) { return X(i) == X(j) ? 1e18 : (Y(i) - Y(j)) / (X(i) - X(j)); }
int main() {
    n = read(), W = read();
    scanf("%s", ch + 1);
    FOR(i, 1, n) {
        w[i] = w[i - 1] + (ch[i] == '+');
        c[i] = c[i - 1] + (ch[i] == '?');
    }
    FOR(i, 1, n) { s[i] = s[i - 1] + w[i] * (ch[i] == '?'); }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    // FOR(i, 1, n) {
    //     int id = 0;
    //     FOR(j, 0, i - 1) {
    //         if (g[j] - c[i] * w[j] + s[i] + W < f[i]) {
    //             f[i] = g[j] - c[i] * w[j] + s[i] + W;
    //             id = j;
    //         }
    //     }
    //     printf("%d %d %lld\n", i, id, f[i]);
    //     g[i] = f[i] - s[i] + c[i] * w[i];
    // }
    q[hd = tl = 1] = 0;
    FOR(i, 1, n) {
        while (hd < tl && g[q[hd + 1]] - g[q[hd]] <= c[i] * (w[q[hd + 1]] - w[q[hd]])) ++hd;
        f[i] = g[q[hd]] - c[i] * w[q[hd]] + s[i] + W;
        g[i] = f[i] - s[i] + c[i] * w[i];
        while (hd < tl && (g[i] - g[q[tl - 1]]) * (w[q[tl]] - w[q[tl - 1]]) <= (g[q[tl]] - g[q[tl - 1]]) * (w[i] - w[q[tl - 1]])) --tl;
        q[++tl] = i;
    }
    printf("%lld\n", f[n] - W);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 17648kb

input:

6 5
++??+?

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6 8
++??+?

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 3ms
memory: 17684kb

input:

5 1
+++++

output:

0

result:

ok single line: '0'

Test #4:

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

input:

10 0
++?+??++??

output:

0

result:

ok single line: '0'

Test #5:

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

input:

12 100
+?+++??+??++

output:

19

result:

ok single line: '19'

Test #6:

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

input:

1 1
?

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 5ms
memory: 17768kb

input:

9 7
++++++++?

output:

7

result:

ok single line: '7'

Test #8:

score: 0
Accepted
time: 4ms
memory: 17748kb

input:

9 8
++++++++?

output:

8

result:

ok single line: '8'

Test #9:

score: 0
Accepted
time: 3ms
memory: 17744kb

input:

10 15
++++++++??

output:

15

result:

ok single line: '15'

Test #10:

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

input:

5 3
+?+?+

output:

3

result:

ok single line: '3'

Test #11:

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

input:

10 5
+?+?+??+??

output:

10

result:

ok single line: '10'

Test #12:

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

input:

10 7
+?+?+??+??

output:

12

result:

ok single line: '12'

Test #13:

score: 0
Accepted
time: 9ms
memory: 17684kb

input:

15 4
+?+?+??+??+??+?

output:

14

result:

ok single line: '14'

Test #14:

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

input:

15 6
+?+?+??+??+??+?

output:

18

result:

ok single line: '18'

Test #15:

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

input:

19 8
+?+?+??+??+??+?++??

output:

28

result:

ok single line: '28'

Test #16:

score: 0
Accepted
time: 9ms
memory: 17756kb

input:

20 9
+?+?+??+??+??+?++???

output:

30

result:

ok single line: '30'

Test #17:

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

input:

500 100
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++++...

output:

2710

result:

ok single line: '2710'

Test #18:

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

input:

10000 100
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++...

output:

56616

result:

ok single line: '56616'

Test #19:

score: 0
Accepted
time: 17ms
memory: 29976kb

input:

500000 3000
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????...

output:

17820759

result:

ok single line: '17820759'

Test #20:

score: 0
Accepted
time: 28ms
memory: 43880kb

input:

1000000 3000
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++????...

output:

35626062

result:

ok single line: '35626062'

Test #21:

score: 0
Accepted
time: 35ms
memory: 43984kb

input:

1000000 1000
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++????...

output:

19934461

result:

ok single line: '19934461'

Test #22:

score: 0
Accepted
time: 23ms
memory: 45936kb

input:

1000000 10000
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++???...

output:

66661466

result:

ok single line: '66661466'

Test #23:

score: 0
Accepted
time: 43ms
memory: 43864kb

input:

1000000 30000
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++???...

output:

117384143

result:

ok single line: '117384143'

Test #24:

score: 0
Accepted
time: 23ms
memory: 43984kb

input:

1000000 500000
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++??...

output:

490361116

result:

ok single line: '490361116'

Test #25:

score: 0
Accepted
time: 35ms
memory: 45308kb

input:

1000000 1000000
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?...

output:

695515718

result:

ok single line: '695515718'

Test #26:

score: 0
Accepted
time: 22ms
memory: 43688kb

input:

1000000 924
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

924

result:

ok single line: '924'

Test #27:

score: 0
Accepted
time: 12ms
memory: 43820kb

input:

1000000 69971
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

69971

result:

ok single line: '69971'

Test #28:

score: 0
Accepted
time: 16ms
memory: 45664kb

input:

1000000 275229
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

275229

result:

ok single line: '275229'

Test #29:

score: 0
Accepted
time: 14ms
memory: 43732kb

input:

1000000 275886
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

275886

result:

ok single line: '275886'

Test #30:

score: 0
Accepted
time: 8ms
memory: 45064kb

input:

1000000 55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

2750

result:

ok single line: '2750'

Test #31:

score: 0
Accepted
time: 12ms
memory: 45376kb

input:

1000000 55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

27500

result:

ok single line: '27500'

Test #32:

score: 0
Accepted
time: 22ms
memory: 47728kb

input:

1000000 0
++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++??????????++++++++++...

output:

0

result:

ok single line: '0'

Test #33:

score: 0
Accepted
time: 21ms
memory: 43856kb

input:

1000000 4
+++++++++++++++++++++++++++++++++?????????????????????????????????+++++++++++++++++++++++++++++++++?????????????????????????????????+++++++++++++++++++++++++++++++++?????????????????????????????????+++++++++++++++++++++++++++++++++?????????????????????????????????++++++++++++++++++++++++++...

output:

60608

result:

ok single line: '60608'

Test #34:

score: 0
Accepted
time: 27ms
memory: 47296kb

input:

1000000 1
+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?...

output:

500000

result:

ok single line: '500000'

Test #35:

score: 0
Accepted
time: 36ms
memory: 46896kb

input:

1000000 1000000
+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?+?...

output:

705858800

result:

ok single line: '705858800'

Test #36:

score: 0
Accepted
time: 10ms
memory: 43848kb

input:

1000000 822
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

7398

result:

ok single line: '7398'

Test #37:

score: 0
Accepted
time: 14ms
memory: 44828kb

input:

1000000 924
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

179256

result:

ok single line: '179256'

Test #38:

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

input:

1000000 0
++++++++++??????????+++++++++++++++++++++++++++++++++++???????????????????????????????????++++++++++++++++++++????????????????????+++++++++++++++++++++++++++++++++?????????????????????????????????++++++++++++++++++++++++++++++++++++????????????????????????????????????++++????++++++++++++++...

output:

0

result:

ok single line: '0'

Test #39:

score: 0
Accepted
time: 4ms
memory: 43868kb

input:

1000000 69971
?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++????...

output:

180870046

result:

ok single line: '180870046'

Test #40:

score: 0
Accepted
time: 29ms
memory: 43860kb

input:

1000000 69971
?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++????...

output:

180835657

result:

ok single line: '180835657'

Test #41:

score: 0
Accepted
time: 24ms
memory: 43980kb

input:

1000000 822
?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????+...

output:

17939203

result:

ok single line: '17939203'

Test #42:

score: 0
Accepted
time: 4ms
memory: 46012kb

input:

1000000 924
?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????+...

output:

19239363

result:

ok single line: '19239363'

Test #43:

score: 0
Accepted
time: 17ms
memory: 45556kb

input:

1000000 924
?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+...

output:

17839350

result:

ok single line: '17839350'

Test #44:

score: 0
Accepted
time: 18ms
memory: 46020kb

input:

1000000 822
?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++?+?+??+??+??+?++?????++??+?+????????????...

output:

18116120

result:

ok single line: '18116120'

Test #45:

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

input:

1000000 972519
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++??...

output:

685792922

result:

ok single line: '685792922'

Test #46:

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

input:

500000 570465
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++???...

output:

261665426

result:

ok single line: '261665426'

Test #47:

score: 0
Accepted
time: 3ms
memory: 19092kb

input:

100000 74846
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++????...

output:

18660523

result:

ok single line: '18660523'

Test #48:

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

input:

2879 999609
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????...

output:

999126

result:

ok single line: '999126'

Test #49:

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

input:

2879 999609
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????...

output:

999126

result:

ok single line: '999126'

Test #50:

score: 0
Accepted
time: 14ms
memory: 43868kb

input:

1000000 822
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

8220

result:

ok single line: '8220'

Test #51:

score: 0
Accepted
time: 9ms
memory: 43848kb

input:

1000000 924
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

1848000

result:

ok single line: '1848000'

Test #52:

score: 0
Accepted
time: 17ms
memory: 45424kb

input:

1000000 55
+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+?????????+????????...

output:

2724973

result:

ok single line: '2724973'

Test #53:

score: 0
Accepted
time: 9ms
memory: 43868kb

input:

1000000 822
+++++???????????????????????????????????????????????????????????????????????????????????????????????+++++???????????????????????????????????????????????????????????????????????????????????????????????+++++???????????????????????????????????????????????????????????????????????????????????...

output:

6485000

result:

ok single line: '6485000'

Test #54:

score: 0
Accepted
time: 28ms
memory: 45676kb

input:

1000000 55
+++++++++++++++++++++++++++++++++++++++++++++?????+++++++++++++++++++++++++++++++++++++++++++++?????+++++++++++++++++++++++++++++++++++++++++++++?????+++++++++++++++++++++++++++++++++++++++++++++?????+++++++++++++++++++++++++++++++++++++++++++++?????+++++++++++++++++++++++++++++++++++++++...

output:

1100000

result:

ok single line: '1100000'

Test #55:

score: 0
Accepted
time: 9ms
memory: 43772kb

input:

1000000 3681
++++++++++?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

368100

result:

ok single line: '368100'

Test #56:

score: 0
Accepted
time: 21ms
memory: 45732kb

input:

1000000 73257
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

output:

48789162

result:

ok single line: '48789162'

Test #57:

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

input:

32 8
+??+?++??++?+??+?++?+??++??+?++?

output:

45

result:

ok single line: '45'

Test #58:

score: 0
Accepted
time: 3ms
memory: 17728kb

input:

1024 20
+??+?++??++?+??+?++?+??++??+?++??++?+??++??+?++?+??+?++??++?+??+?++?+??++??+?++?+??+?++??++?+??++??+?++??++?+??+?++?+??++??+?++??++?+??++??+?++?+??+?++??++?+??++??+?++??++?+??+?++?+??++??+?++?+??+?++??++?+??+?++?+??++??+?++??++?+??++??+?++?+??+?++??++?+??+?++?+??++??+?++?+??+?++??++?+??++??+...

output:

2726

result:

ok single line: '2726'

Test #59:

score: 0
Accepted
time: 7ms
memory: 33176kb

input:

524288 1000
+??+?++??++?+??+?++?+??++??+?++??++?+??++??+?++?+??+?++??++?+??+?++?+??++??+?++?+??+?++??++?+??++??+?++??++?+??+?++?+??++??+?++??++?+??++??+?++?+??+?++??++?+??++??+?++??++?+??+?++?+??++??+?++?+??+?++??++?+??+?++?+??++??+?++??++?+??++??+?++?+??+?++??++?+??+?++?+??++??+?++?+??+?++??++?+??+...

output:

11461382

result:

ok single line: '11461382'

Test #60:

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

input:

524288 10000
+??+?++??++?+??+?++?+??++??+?++??++?+??++??+?++?+??+?++??++?+??+?++?+??++??+?++?+??+?++??++?+??++??+?++??++?+??+?++?+??++??+?++??++?+??++??+?++?+??+?++??++?+??++??+?++??++?+??+?++?+??++??+?++?+??+?++??++?+??+?++?+??++??+?++??++?+??++??+?++?+??+?++??++?+??+?++?+??++??+?++?+??+?++??++?+??...

output:

36801050

result:

ok single line: '36801050'