제출 #105569

#제출 시각아이디문제언어결과실행 시간메모리
105569Pro_ktmrLamps (JOI19_lamps)C++14
47 / 100
1068 ms209932 KiB
#pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include"bits/stdc++.h" using namespace std; #define LL long long #define MP make_pair #define PB push_back int N; string A = ""; string B = ""; string allPatern[16] = {"","F","N","X","FN","NF","NX","XN","XF","FX","FNX","FXN","NFX","NXF","XFN","XNF"}; LL memo[16][16]; LL culc(int moto, int ato){ string A = allPatern[moto]; string B = allPatern[ato]; for(int i=3; i>=1; i--){ //length for(int j=0; j+i-1<A.size(); j++){ for(int k=0; k+i-1<B.size(); k++){ for(int l=0; l<i; l++){ if(A[j+l] != B[k+l]) break; if(l == i-1) return B.size()-i; } } } } return B.size(); } LL dp[1000000][16]; bool already[1000000][16] = {}; LL solve(int now, int order){ if(now == N) return 0; if(already[now][order]) return dp[now][order]; already[now][order] = true; //cout << now << " " << order << endl; LL ans = LLONG_MAX; for(int i=0; i<16; i++){ if(allPatern[i].back() == 'F' && B[now] == '1') continue; if(allPatern[i].back() == 'N' && B[now] == '0') continue; int tmp = A[now]-'0'; for(int j=0; j<allPatern[i].size(); j++){ if(allPatern[i][j] == 'F') tmp = 0; if(allPatern[i][j] == 'N') tmp = 1; if(allPatern[i][j] == 'X') tmp = tmp ^ 1; } if(tmp != B[now]-'0') continue; ans = min(ans, memo[order][i]+solve(now+1,i)); } return dp[now][order] = ans; } int main(){ scanf("%d", &N); for(int i=0; i<16; i++){ for(int j=0; j<16; j++){ memo[i][j] = culc(i, j); } } cin >> A >> B; cout << solve(0, 0) << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

lamp.cpp: In function 'long long int culc(int, int)':
lamp.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j+i-1<A.size(); j++){
                ~~~~~^~~~~~~~~
lamp.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k+i-1<B.size(); k++){
                 ~~~~~^~~~~~~~~
lamp.cpp: In function 'long long int solve(int, int)':
lamp.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<allPatern[i].size(); j++){
                ~^~~~~~~~~~~~~~~~~~~~
lamp.cpp: In function 'int main()':
lamp.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...