답안 #427241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427241	2021-06-14T13:41:14 Z	cpp219	Lamps (JOI19_lamps)	C++14	100 / 100	214 ms	145200 KB

lamp

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e6 + 9;
const ll inf = 1e9 + 7;
const ll Log2 = 20;
typedef pair<ll,ll> LL;

string s,p;
ll n,dp[N][3][2];

ll convert(ll now,ll zo,ll flip){
    if (zo == 1) now = 0;
    if (zo == 2) now = 1;
    if (flip) now = 1 - now;
    return now;
}

ll f(ll pos,ll zo,ll flip){
    if (pos > n) return 0;
    if (dp[pos][zo][flip] != -1) return dp[pos][zo][flip];
    ll now = s[pos] - '0',ans = inf;
    for (ll i = 0;i < 3;i++)
        for (ll j = 0;j < 2;j++){
            ll cur = convert(now,i,j),cost = 0;
            if (i && i != zo) cost++;
            if (j && j != flip) cost++;
            if (cur == p[pos] - '0') ans = min(ans,cost + f(pos + 1,i,j));
        }
    return dp[pos][zo][flip] = ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>s>>p; s = " " + s; p = " " + p;
    memset(dp,-1,sizeof(dp));
    cout<<f(1,0,0);
}

Compilation message

lamp.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
lamp.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
lamp.cpp: In function 'int main()':
lamp.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	47308 KB	Output is correct
2	Correct	21 ms	47228 KB	Output is correct
3	Correct	20 ms	47180 KB	Output is correct
4	Correct	20 ms	47196 KB	Output is correct
5	Correct	20 ms	47200 KB	Output is correct
6	Correct	20 ms	47164 KB	Output is correct
7	Correct	20 ms	47204 KB	Output is correct
8	Correct	23 ms	47148 KB	Output is correct
9	Correct	21 ms	47176 KB	Output is correct
10	Correct	22 ms	47328 KB	Output is correct
11	Correct	21 ms	47212 KB	Output is correct
12	Correct	22 ms	47180 KB	Output is correct
13	Correct	23 ms	47164 KB	Output is correct
14	Correct	21 ms	47180 KB	Output is correct
15	Correct	21 ms	47192 KB	Output is correct
16	Correct	24 ms	47260 KB	Output is correct
17	Correct	22 ms	47168 KB	Output is correct
18	Correct	21 ms	47180 KB	Output is correct
19	Correct	20 ms	47236 KB	Output is correct
20	Correct	21 ms	47220 KB	Output is correct
21	Correct	20 ms	47256 KB	Output is correct
22	Correct	21 ms	47180 KB	Output is correct
23	Correct	21 ms	47180 KB	Output is correct
24	Correct	21 ms	47180 KB	Output is correct
25	Correct	20 ms	47180 KB	Output is correct
26	Correct	21 ms	47204 KB	Output is correct
27	Correct	21 ms	47244 KB	Output is correct
28	Correct	20 ms	47180 KB	Output is correct
29	Correct	22 ms	47232 KB	Output is correct
30	Correct	23 ms	47180 KB	Output is correct
31	Correct	22 ms	47172 KB	Output is correct
32	Correct	21 ms	47200 KB	Output is correct
33	Correct	23 ms	47236 KB	Output is correct
34	Correct	24 ms	47188 KB	Output is correct

Subtask #2
41.0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	47308 KB	Output is correct
2	Correct	21 ms	47228 KB	Output is correct
3	Correct	20 ms	47180 KB	Output is correct
4	Correct	20 ms	47196 KB	Output is correct
5	Correct	20 ms	47200 KB	Output is correct
6	Correct	20 ms	47164 KB	Output is correct
7	Correct	20 ms	47204 KB	Output is correct
8	Correct	23 ms	47148 KB	Output is correct
9	Correct	21 ms	47176 KB	Output is correct
10	Correct	22 ms	47328 KB	Output is correct
11	Correct	21 ms	47212 KB	Output is correct
12	Correct	22 ms	47180 KB	Output is correct
13	Correct	23 ms	47164 KB	Output is correct
14	Correct	21 ms	47180 KB	Output is correct
15	Correct	21 ms	47192 KB	Output is correct
16	Correct	24 ms	47260 KB	Output is correct
17	Correct	22 ms	47168 KB	Output is correct
18	Correct	21 ms	47180 KB	Output is correct
19	Correct	20 ms	47236 KB	Output is correct
20	Correct	21 ms	47220 KB	Output is correct
21	Correct	20 ms	47256 KB	Output is correct
22	Correct	21 ms	47180 KB	Output is correct
23	Correct	21 ms	47180 KB	Output is correct
24	Correct	21 ms	47180 KB	Output is correct
25	Correct	20 ms	47180 KB	Output is correct
26	Correct	21 ms	47204 KB	Output is correct
27	Correct	21 ms	47244 KB	Output is correct
28	Correct	20 ms	47180 KB	Output is correct
29	Correct	22 ms	47232 KB	Output is correct
30	Correct	23 ms	47180 KB	Output is correct
31	Correct	22 ms	47172 KB	Output is correct
32	Correct	21 ms	47200 KB	Output is correct
33	Correct	23 ms	47236 KB	Output is correct
34	Correct	24 ms	47188 KB	Output is correct
35	Correct	20 ms	47428 KB	Output is correct
36	Correct	22 ms	47376 KB	Output is correct
37	Correct	23 ms	47456 KB	Output is correct
38	Correct	21 ms	47456 KB	Output is correct
39	Correct	20 ms	47436 KB	Output is correct
40	Correct	22 ms	47436 KB	Output is correct
41	Correct	22 ms	47392 KB	Output is correct
42	Correct	21 ms	47428 KB	Output is correct
43	Correct	21 ms	47388 KB	Output is correct
44	Correct	22 ms	47436 KB	Output is correct
45	Correct	22 ms	47400 KB	Output is correct
46	Correct	21 ms	47436 KB	Output is correct
47	Correct	21 ms	47436 KB	Output is correct
48	Correct	21 ms	47440 KB	Output is correct
49	Correct	22 ms	47472 KB	Output is correct
50	Correct	22 ms	47352 KB	Output is correct
51	Correct	22 ms	47440 KB	Output is correct
52	Correct	22 ms	47436 KB	Output is correct
53	Correct	21 ms	47428 KB	Output is correct
54	Correct	21 ms	47436 KB	Output is correct
55	Correct	20 ms	47424 KB	Output is correct
56	Correct	21 ms	47436 KB	Output is correct
57	Correct	21 ms	47400 KB	Output is correct
58	Correct	23 ms	47372 KB	Output is correct

Subtask #3
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	47200 KB	Output is correct
2	Correct	25 ms	47164 KB	Output is correct
3	Correct	21 ms	47256 KB	Output is correct
4	Correct	23 ms	47216 KB	Output is correct
5	Correct	25 ms	47180 KB	Output is correct
6	Correct	23 ms	47176 KB	Output is correct
7	Correct	150 ms	145076 KB	Output is correct
8	Correct	176 ms	145052 KB	Output is correct
9	Correct	152 ms	145008 KB	Output is correct
10	Correct	158 ms	145080 KB	Output is correct
11	Correct	150 ms	144996 KB	Output is correct
12	Correct	150 ms	145072 KB	Output is correct
13	Correct	174 ms	145028 KB	Output is correct
14	Correct	156 ms	145092 KB	Output is correct

Subtask #4
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	47308 KB	Output is correct
2	Correct	21 ms	47228 KB	Output is correct
3	Correct	20 ms	47180 KB	Output is correct
4	Correct	20 ms	47196 KB	Output is correct
5	Correct	20 ms	47200 KB	Output is correct
6	Correct	20 ms	47164 KB	Output is correct
7	Correct	20 ms	47204 KB	Output is correct
8	Correct	23 ms	47148 KB	Output is correct
9	Correct	21 ms	47176 KB	Output is correct
10	Correct	22 ms	47328 KB	Output is correct
11	Correct	21 ms	47212 KB	Output is correct
12	Correct	22 ms	47180 KB	Output is correct
13	Correct	23 ms	47164 KB	Output is correct
14	Correct	21 ms	47180 KB	Output is correct
15	Correct	21 ms	47192 KB	Output is correct
16	Correct	24 ms	47260 KB	Output is correct
17	Correct	22 ms	47168 KB	Output is correct
18	Correct	21 ms	47180 KB	Output is correct
19	Correct	20 ms	47236 KB	Output is correct
20	Correct	21 ms	47220 KB	Output is correct
21	Correct	20 ms	47256 KB	Output is correct
22	Correct	21 ms	47180 KB	Output is correct
23	Correct	21 ms	47180 KB	Output is correct
24	Correct	21 ms	47180 KB	Output is correct
25	Correct	20 ms	47180 KB	Output is correct
26	Correct	21 ms	47204 KB	Output is correct
27	Correct	21 ms	47244 KB	Output is correct
28	Correct	20 ms	47180 KB	Output is correct
29	Correct	22 ms	47232 KB	Output is correct
30	Correct	23 ms	47180 KB	Output is correct
31	Correct	22 ms	47172 KB	Output is correct
32	Correct	21 ms	47200 KB	Output is correct
33	Correct	23 ms	47236 KB	Output is correct
34	Correct	24 ms	47188 KB	Output is correct
35	Correct	20 ms	47428 KB	Output is correct
36	Correct	22 ms	47376 KB	Output is correct
37	Correct	23 ms	47456 KB	Output is correct
38	Correct	21 ms	47456 KB	Output is correct
39	Correct	20 ms	47436 KB	Output is correct
40	Correct	22 ms	47436 KB	Output is correct
41	Correct	22 ms	47392 KB	Output is correct
42	Correct	21 ms	47428 KB	Output is correct
43	Correct	21 ms	47388 KB	Output is correct
44	Correct	22 ms	47436 KB	Output is correct
45	Correct	22 ms	47400 KB	Output is correct
46	Correct	21 ms	47436 KB	Output is correct
47	Correct	21 ms	47436 KB	Output is correct
48	Correct	21 ms	47440 KB	Output is correct
49	Correct	22 ms	47472 KB	Output is correct
50	Correct	22 ms	47352 KB	Output is correct
51	Correct	22 ms	47440 KB	Output is correct
52	Correct	22 ms	47436 KB	Output is correct
53	Correct	21 ms	47428 KB	Output is correct
54	Correct	21 ms	47436 KB	Output is correct
55	Correct	20 ms	47424 KB	Output is correct
56	Correct	21 ms	47436 KB	Output is correct
57	Correct	21 ms	47400 KB	Output is correct
58	Correct	23 ms	47372 KB	Output is correct
59	Correct	21 ms	47200 KB	Output is correct
60	Correct	25 ms	47164 KB	Output is correct
61	Correct	21 ms	47256 KB	Output is correct
62	Correct	23 ms	47216 KB	Output is correct
63	Correct	25 ms	47180 KB	Output is correct
64	Correct	23 ms	47176 KB	Output is correct
65	Correct	150 ms	145076 KB	Output is correct
66	Correct	176 ms	145052 KB	Output is correct
67	Correct	152 ms	145008 KB	Output is correct
68	Correct	158 ms	145080 KB	Output is correct
69	Correct	150 ms	144996 KB	Output is correct
70	Correct	150 ms	145072 KB	Output is correct
71	Correct	174 ms	145028 KB	Output is correct
72	Correct	156 ms	145092 KB	Output is correct
73	Correct	152 ms	145044 KB	Output is correct
74	Correct	169 ms	145096 KB	Output is correct
75	Correct	156 ms	145008 KB	Output is correct
76	Correct	150 ms	145084 KB	Output is correct
77	Correct	152 ms	145056 KB	Output is correct
78	Correct	161 ms	145108 KB	Output is correct
79	Correct	159 ms	145200 KB	Output is correct
80	Correct	150 ms	145020 KB	Output is correct
81	Correct	184 ms	145004 KB	Output is correct
82	Correct	161 ms	145052 KB	Output is correct
83	Correct	177 ms	145152 KB	Output is correct
84	Correct	186 ms	145052 KB	Output is correct
85	Correct	169 ms	145084 KB	Output is correct
86	Correct	179 ms	145040 KB	Output is correct
87	Correct	177 ms	145116 KB	Output is correct
88	Correct	173 ms	145028 KB	Output is correct
89	Correct	176 ms	145120 KB	Output is correct
90	Correct	201 ms	145092 KB	Output is correct
91	Correct	189 ms	145064 KB	Output is correct
92	Correct	182 ms	145096 KB	Output is correct
93	Correct	196 ms	145000 KB	Output is correct
94	Correct	179 ms	145020 KB	Output is correct
95	Correct	191 ms	145052 KB	Output is correct
96	Correct	214 ms	145124 KB	Output is correct
97	Correct	188 ms	145168 KB	Output is correct
98	Correct	192 ms	145076 KB	Output is correct
99	Correct	193 ms	145128 KB	Output is correct
100	Correct	192 ms	145148 KB	Output is correct
101	Correct	186 ms	145004 KB	Output is correct
102	Correct	191 ms	145012 KB	Output is correct

답안 #427241

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 41.0 / 41.0

Subtask #3 4.0 / 4.0

Subtask #4 49.0 / 49.0

Subtask #1
6.0 / 6.0

Subtask #2
41.0 / 41.0

Subtask #3
4.0 / 4.0

Subtask #4
49.0 / 49.0