QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#59525#3894. Generator GridHawaraAC ✓62ms81188kbC++141.6kb2022-10-30 08:02:052022-10-30 08:02:07

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-30 08:02:07]
  • Judged
  • Verdict: AC
  • Time: 62ms
  • Memory: 81188kb
Show
  • [2022-10-30 08:02:05]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("-Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#define IO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define ll long long
const long long MOD = 1e9 + 7, OO = 1e18;
const double PI = acos(-1);
const int N = 1e6 + 5;
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

ll n, m, pl[N], u, v, mem[N][2][2][2];
pair<ll, ll> plant[N];

ll dp(ll i, bool pre, bool final, bool ok)
{   
    if (i == n)return (ok == 0) * OO;

    ll &ret = mem[i][pre][final][ok];
    if (~ret)return ret;

    ll c1 = OO, c2 = OO, c3 = OO;
    if (plant[i].first)
    {
        c1 = plant[i].second + dp(i + 1, 0, final, 1);
    }
    if (pre == 0)
    {
        ll prev = i - 1;
        if (prev == 0)prev = n;
        c2 = pl[prev] + dp(i + 1, 0, final, ok);
    }
    if (i != n - 1 || (i == n - 1 && final))
    {
        c3 = pl[i] + dp(i + 1, 1, final, ok);
    }

    return ret = min({c1, c2, c3});
}

int main()
{
    IO
    memset(mem, -1, sizeof mem);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        plant[u] = {1, v};
    }
    for (int i = 1; i <= n; i++)cin >> pl[i];

    ll c1 = plant[n].first ? plant[n].second + dp(1, 0, 1, 1) : OO;
    ll c2 = pl[n] + dp(1, 1, 1, 0);
    ll c3 = pl[n - 1] + dp(1, 0, 0, 0);

    cout << min({c1, c2, c3});
    return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 66188kb

input:

3 2
1 100
2 200
150 300 150

output:

400

result:

ok single line: '400'

Test #2:

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

input:

3 2
1 100
2 200
300 300 150

output:

450

result:

ok single line: '450'

Test #3:

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

input:

100 1
1 100
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

1090

result:

ok single line: '1090'

Test #4:

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

input:

100 100
1 100
2 100
3 100
4 100
5 100
6 100
7 100
8 100
9 100
10 100
11 100
12 100
13 100
14 100
15 100
16 100
17 100
18 100
19 100
20 100
21 100
22 100
23 100
24 100
25 100
26 100
27 100
28 100
29 100
30 100
31 100
32 100
33 100
34 100
35 100
36 100
37 100
38 100
39 100
40 100
41 100
42 100
43 100
...

output:

1090

result:

ok single line: '1090'

Test #5:

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

input:

100 100
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
10 10
11 10
12 10
13 10
14 10
15 10
16 10
17 10
18 10
19 10
20 10
21 10
22 10
23 10
24 10
25 10
26 10
27 10
28 10
29 10
30 10
31 10
32 10
33 10
34 10
35 10
36 10
37 10
38 10
39 10
40 10
41 10
42 10
43 10
44 10
45 10
46 10
47 10
48 10
49 10
50 10
5...

output:

1000

result:

ok single line: '1000'

Test #6:

score: 0
Accepted
time: 49ms
memory: 81016kb

input:

100000 100000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
6 1000000000
7 1000000000
8 1000000000
9 1000000000
10 1000000000
11 1000000000
12 1000000000
13 1000000000
14 1000000000
15 1000000000
16 1000000000
17 1000000000
18 1000000000
19 1000000000
20 1000000000
21 1000000000
2...

output:

100000000000000

result:

ok single line: '100000000000000'

Test #7:

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

input:

3 1
1 1
1 1 1

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 62ms
memory: 80448kb

input:

100000 74767
1 138940954
3 19986181
5 695152941
10 25582537
11 140007031
12 569374311
13 525539419
14 469038348
15 801427429
17 726991668
18 93743389
19 428218490
20 814325266
21 828939972
22 199634162
24 681381870
25 764678772
26 999070500
27 348411791
28 17375761
29 102004979
30 671397756
32 29838...

output:

32622097081612

result:

ok single line: '32622097081612'

Test #9:

score: 0
Accepted
time: 44ms
memory: 79980kb

input:

100000 75072
1 119746883
3 567224023
5 236735954
6 644263306
7 690087020
8 256898655
9 402453894
10 966077571
11 705655080
12 460289341
13 111194245
14 514395641
15 487945388
16 393770539
17 609245894
18 795640814
19 884967034
20 36777744
21 972898642
22 458083868
23 959502163
24 381853217
26 804632...

output:

32468792065853

result:

ok single line: '32468792065853'

Test #10:

score: 0
Accepted
time: 38ms
memory: 81040kb

input:

100000 74950
1 27496248
2 510198024
3 354246088
4 357948794
5 739134363
6 49594174
7 934676405
8 875970958
10 793478985
11 698720316
12 287660286
13 624981626
14 770979636
15 216437636
16 901886683
17 518558415
18 203942753
19 386862613
20 497838496
21 661896619
23 550532627
24 245721502
25 74073985...

output:

32644363126004

result:

ok single line: '32644363126004'

Test #11:

score: 0
Accepted
time: 41ms
memory: 80384kb

input:

100000 74898
1 169764218
2 949427897
3 630976586
4 687396582
5 694825678
6 427323803
7 468814686
8 4111483
9 321958510
10 963838243
11 849102982
13 442903289
14 149713351
15 800043897
17 486763508
18 650468579
20 963903854
21 811855680
22 14155508
23 317160096
24 750805176
25 574459305
26 698592586
...

output:

32553609448513

result:

ok single line: '32553609448513'

Test #12:

score: 0
Accepted
time: 40ms
memory: 80260kb

input:

100000 75000
2 306596109
3 998829041
6 40752489
7 857492043
8 710684156
9 492118329
10 400971952
12 506117713
13 637557606
14 823768348
16 123891874
17 156365518
19 963296915
20 787811908
21 141181174
22 195625676
23 347188165
24 904497413
26 783040277
27 767484081
29 178077486
30 722930152
31 89848...

output:

32578004759315

result:

ok single line: '32578004759315'

Test #13:

score: 0
Accepted
time: 38ms
memory: 79948kb

input:

100000 75028
1 1
2 2
6 1
7 1
10 2
11 2
12 1
13 1
14 1
15 1
17 1
18 1
19 2
20 1
21 1
23 2
24 1
25 1
26 1
27 1
30 1
32 2
33 1
35 2
36 1
37 1
38 1
39 2
40 1
41 2
42 1
43 1
44 1
45 2
47 2
49 1
51 1
52 1
53 2
54 2
55 1
56 2
57 2
58 1
62 2
63 1
65 2
66 2
67 1
68 1
69 1
70 1
72 2
73 2
74 2
76 2
78 1
81 1
8...

output:

122635

result:

ok single line: '122635'

Test #14:

score: 0
Accepted
time: 31ms
memory: 81188kb

input:

100000 75076
1 2
2 2
3 6
4 7
5 6
6 7
7 1
8 1
9 1
10 6
11 4
12 3
13 4
14 3
15 10
19 5
20 9
21 9
23 6
24 2
25 7
26 10
27 4
29 7
30 10
31 3
32 7
33 5
35 5
37 1
38 1
39 3
40 10
41 6
42 1
43 10
44 4
45 5
46 8
47 9
49 4
50 1
51 6
53 5
54 10
57 6
59 4
60 7
61 1
62 4
66 8
69 1
70 10
71 1
73 9
74 2
77 4
80 3...

output:

377760

result:

ok single line: '377760'

Test #15:

score: 0
Accepted
time: 34ms
memory: 80600kb

input:

100000 75134
1 80
2 78
3 63
4 71
5 93
7 54
9 54
10 25
11 57
12 14
13 63
14 56
15 7
16 52
18 32
21 40
22 52
23 78
25 10
26 8
27 85
28 70
29 38
30 95
32 54
33 1
34 83
35 61
36 55
38 29
39 90
40 48
41 39
42 81
43 68
44 9
46 37
48 75
49 69
51 69
52 42
53 64
54 70
57 85
58 97
61 31
62 5
64 18
65 36
66 11...

output:

3311611

result:

ok single line: '3311611'

Test #16:

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

input:

100000 100000
1 4
2 2
3 4
4 2
5 4
6 2
7 4
8 2
9 4
10 2
11 4
12 2
13 4
14 2
15 4
16 2
17 4
18 2
19 4
20 2
21 4
22 2
23 4
24 2
25 4
26 2
27 4
28 2
29 4
30 2
31 4
32 2
33 4
34 2
35 4
36 2
37 4
38 2
39 4
40 2
41 4
42 2
43 4
44 2
45 4
46 2
47 4
48 2
49 4
50 2
51 4
52 2
53 4
54 2
55 4
56 2
57 4
58 2
59 4
...

output:

150000

result:

ok single line: '150000'

Test #17:

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

input:

100000 100000
1 3
2 2
3 3
4 2
5 3
6 2
7 3
8 2
9 3
10 2
11 3
12 2
13 3
14 2
15 3
16 2
17 3
18 2
19 3
20 2
21 3
22 2
23 3
24 2
25 3
26 2
27 3
28 2
29 3
30 2
31 3
32 2
33 3
34 2
35 3
36 2
37 3
38 2
39 3
40 2
41 3
42 2
43 3
44 2
45 3
46 2
47 3
48 2
49 3
50 2
51 3
52 2
53 3
54 2
55 3
56 2
57 3
58 2
59 3
...

output:

150000

result:

ok single line: '150000'
English 繁體中文 简体中文

伺服器時間: 2025-02-08 19:08:53 | 開源專案