제출 #1082403

#제출 시각아이디문제언어결과실행 시간메모리
1082403phongLamps (JOI19_lamps)C++17
4 / 100
274 ms173488 KiB
#include<bits/stdc++.h> #define ll long long const int nmax = 1e6 + 5, N = 1e5; const ll oo = 1e18 + 1, base = 311; const int lg = 15, M = 10; const ll mod = 998244353, mod2 = 1e9 + 5277; #define pii pair<int, int> #define fi first #define se second #define endl "\n" #define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n"; using namespace std; int n; string a, b; int dp[nmax][20 + 1][2]; int deg[nmax]; struct node{ int f[3]; }one[nmax]; int sz = 0, g[nmax], stu[nmax]; int F[2][100]; void add(vector<int> &v){ ++sz; g[sz] = v.size(); if(v.size() >= 1) one[sz].f[0] = v[0]; if(v.size() >= 2) one[sz].f[1] = v[1]; if(v.size() >= 3) one[sz].f[2] = v[2]; int res = 0; for(int i = 0; i < 3; ++i){ res = res * 10 + one[sz].f[i]; } stu[sz] = res; deg[res] = sz; for(int x = 0; x < 2; ++x){ int id = x; for(int i = 0; i < 3; ++i){ if(one[sz].f[i] == 1) id = 0; if(one[sz].f[i] == 2) id = 1; if(one[sz].f[i] == 3) id ^= 1; } F[x][sz] = id; } } vector<pii> adj[100], gg[100]; main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("code.inp", "r", stdin); // freopen("code.out", "w", stdout); cin >> n; cin >> a; cin >> b; a = ' ' + a; b = ' ' + b; memset(dp, 0x3f, sizeof dp); dp[0][0][0] = 0; vector<int> v; for(int i = 1; i <= 3; ++i){ v.push_back(i); do{ add(v); } while(next_permutation(v.begin(), v.end())); v.clear(); } for(int i = 1; i <= 3; ++i){ for(int j = i + 1; j <= 3; ++j){ v.push_back(i); v.push_back(j); do{ add(v); } while(next_permutation(v.begin(), v.end())); v.clear(); } } for(int i = 1; i <= 3; ++i) v.push_back(i); do{ add(v); } while(next_permutation(v.begin(), v.end())); v.clear(); for(int i = 0; i <= sz; ++i){ for(int j = 0; j <= sz; ++j){ if(g[i] + g[j] <= 3){ bool ok = 1; for(int x = 0; x < 3; ++x){ if(!one[i].f[x]) break; for(int y = 0; y < 3; ++y){ if(!one[j].f[y])break; if(one[i].f[x] == one[j].f[y]) ok = 0; } } if(ok){ int res = 0; for(int x = 0; x < 3; ++x){ if(!one[i].f[x]) break; res = res * 10 + one[i].f[x]; } for(int x = 0; x < 3; ++x){ if(!one[j].f[x]) break; res = res * 10 + one[j].f[x]; } int x = 3 - g[i] - g[j]; while(x > 0){ res *= 10; --x; } adj[i].push_back({deg[res], g[j]}); } } } int res = 0; gg[i].push_back({0, 0}); for(int x = 0; x < 3; ++x){ if(!one[i].f[x]) break; res = res * 10 + one[i].f[x]; int cur = res; for(int j = x + 1; j < 3; ++j) cur *= 10; gg[i].push_back({deg[cur], 0}); } } F[0][0] =0, F[1][0] = 1; for(int i = 0; i < n;++i){ int x; if(i == 0) x = 0; else x = b[i] - '0'; for(int msk = sz; msk >= 0; --msk){ for(auto [new_msk, cost] : adj[msk]){ dp[i][new_msk][x] = min(dp[i][new_msk][x], dp[i][msk][x] + cost); } } for(int msk = sz; msk >= 0; --msk){ for(auto [new_msk, cost] : gg[msk]){ int y = a[i + 1] - '0'; int id = F[y][new_msk]; dp[i + 1][new_msk][id] = min(dp[i + 1][new_msk][id], dp[i][msk][x] + cost); } } } int ans = 1e9; for(int msk = 0; msk <= sz; ++msk) ans = min(ans, dp[n][msk][b[n]-'0']); cout << ans; } /* 5 2 4 8 4 3 4 2 2 1 2 7 6 5 4 10 10 1 2 */

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

lamp.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...