Submission #2325975
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} struct bipartite_matching{ static const int MAX_V=5000; vector<int>G[MAX_V]; int match[MAX_V]; bool used[MAX_V]; void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } bool dfs(int v){ used[v]=true; for(int i=0;i<G[v].size();i++){ int u=G[v][i],w=match[u]; if(w<0||!used[w]&&dfs(w)){ match[v]=u; match[u]=v; return true; } } return false; } int matching(){ int res=0; memset(match,-1,sizeof(match)); for(int v=0;v<MAX_V;v++){ if(match[v]<0){ memset(used,0,sizeof(used)); if(dfs(v))res++; } } return res; } }; int H,W; int A[77][77],B[77][77]; signed main(){ cin>>H>>W; rep(i,H)rep(j,W)cin>>A[i][j]; rep(i,H)rep(j,W)cin>>B[i][j]; bipartite_matching latte; int ans=0; rep(i,H)rep(j,W){ if(A[i][j]==B[i][j])continue; ans++; if(i+1<H){ if(A[i+1][j]!=B[i+1][j]&&A[i][j]!=A[i+1][j])latte.add_edge(i*W+j,(i+1)*W+j); } if(j+1<W){ if(A[i][j+1]!=B[i][j+1]&&A[i][j]!=A[i][j+1])latte.add_edge(i*W+j,i*W+j+1); } } cout<<ans-latte.matching()<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 天下一美術館 |
User | latte0119 |
Language | C++14 (GCC 5.4.1) |
Score | 90 |
Code Size | 1850 Byte |
Status | AC |
Exec Time | 46 ms |
Memory | 896 KB |
Judge Result
Set Name | small | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 40 / 40 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
small | 00_manual03.txt, 00_manual04.txt, 00_manual05.txt, 00_manual06.txt, 00_manual07.txt, 00_sample00.txt, 00_sample01.txt, 00_sample02.txt, 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt, 00_small118.txt, 00_small119.txt, 00_small120.txt, 00_small121.txt, 00_small122.txt, 00_small123.txt, 00_small124.txt, 00_small125.txt, 00_small126.txt, 00_small127.txt, 00_small128.txt, 00_small129.txt, 00_small130.txt, 00_small131.txt, 00_small132.txt, 00_small133.txt, 00_small134.txt, 00_small135.txt, 00_small136.txt, 00_small137.txt, 00_small138.txt, 00_small139.txt, 00_small140.txt, 00_small141.txt, 00_small142.txt, 00_small143.txt, 00_small144.txt, 00_small145.txt, 00_small146.txt, 00_small147.txt, 00_small148.txt, 00_small149.txt, 00_small150.txt, 00_small151.txt, 00_small152.txt, 00_small153.txt, 00_small154.txt, 00_small155.txt, 00_small156.txt, 00_small157.txt, 00_small158.txt |
All | 00_manual03.txt, 00_manual04.txt, 00_manual05.txt, 00_manual06.txt, 00_manual07.txt, 00_sample00.txt, 00_sample01.txt, 00_sample02.txt, 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt, 00_small118.txt, 00_small119.txt, 00_small120.txt, 00_small121.txt, 00_small122.txt, 00_small123.txt, 00_small124.txt, 00_small125.txt, 00_small126.txt, 00_small127.txt, 00_small128.txt, 00_small129.txt, 00_small130.txt, 00_small131.txt, 00_small132.txt, 00_small133.txt, 00_small134.txt, 00_small135.txt, 00_small136.txt, 00_small137.txt, 00_small138.txt, 00_small139.txt, 00_small140.txt, 00_small141.txt, 00_small142.txt, 00_small143.txt, 00_small144.txt, 00_small145.txt, 00_small146.txt, 00_small147.txt, 00_small148.txt, 00_small149.txt, 00_small150.txt, 00_small151.txt, 00_small152.txt, 00_small153.txt, 00_small154.txt, 00_small155.txt, 00_small156.txt, 00_small157.txt, 00_small158.txt, 01_large100.txt, 01_large101.txt, 01_large102.txt, 01_large103.txt, 01_large104.txt, 01_large105.txt, 01_large106.txt, 01_large107.txt, 01_large108.txt, 01_large1325.txt, 01_large1327.txt, 01_large1330.txt, 01_large1339.txt, 01_large1343.txt, 01_large1355.txt, 01_large1366.txt, 01_large1367.txt, 01_large1374.txt, 01_large1380.txt, 01_large1388.txt, 01_large1395.txt, 01_large1396.txt, 01_large1400.txt, 01_large1402.txt, 01_large1405.txt, 01_large1409.txt, 01_large1413.txt, 01_large1417.txt, 01_large1423.txt, 01_large1430.txt, 01_large1437.txt, 01_large1438.txt, 01_large1442.txt, 01_large1450.txt, 01_large1459.txt, 01_large1464.txt, 01_large1472.txt, 01_large1478.txt, 01_large1480.txt, 01_large1486.txt, 01_large1492.txt, 01_large1500.txt, 01_large1501.txt, 01_large1502.txt, 01_large1506.txt, 01_large157.txt, 01_large207.txt, 01_large507.txt, 01_large577.txt, 01_large591.txt, 01_large893.txt, 01_manual_L00.txt, 01_manual_L01.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_manual03.txt | AC | 2 ms | 384 KB |
00_manual04.txt | AC | 2 ms | 384 KB |
00_manual05.txt | AC | 2 ms | 384 KB |
00_manual06.txt | AC | 2 ms | 384 KB |
00_manual07.txt | AC | 2 ms | 384 KB |
00_sample00.txt | AC | 2 ms | 384 KB |
00_sample01.txt | AC | 2 ms | 384 KB |
00_sample02.txt | AC | 2 ms | 384 KB |
00_small100.txt | AC | 2 ms | 384 KB |
00_small101.txt | AC | 2 ms | 384 KB |
00_small102.txt | AC | 2 ms | 384 KB |
00_small103.txt | AC | 2 ms | 384 KB |
00_small104.txt | AC | 2 ms | 384 KB |
00_small105.txt | AC | 2 ms | 384 KB |
00_small106.txt | AC | 2 ms | 384 KB |
00_small107.txt | AC | 2 ms | 384 KB |
00_small108.txt | AC | 2 ms | 384 KB |
00_small109.txt | AC | 2 ms | 384 KB |
00_small110.txt | AC | 2 ms | 384 KB |
00_small111.txt | AC | 2 ms | 384 KB |
00_small112.txt | AC | 2 ms | 384 KB |
00_small113.txt | AC | 2 ms | 384 KB |
00_small114.txt | AC | 2 ms | 384 KB |
00_small115.txt | AC | 2 ms | 384 KB |
00_small116.txt | AC | 2 ms | 384 KB |
00_small117.txt | AC | 2 ms | 384 KB |
00_small118.txt | AC | 2 ms | 384 KB |
00_small119.txt | AC | 2 ms | 384 KB |
00_small120.txt | AC | 2 ms | 384 KB |
00_small121.txt | AC | 2 ms | 384 KB |
00_small122.txt | AC | 2 ms | 384 KB |
00_small123.txt | AC | 2 ms | 384 KB |
00_small124.txt | AC | 2 ms | 384 KB |
00_small125.txt | AC | 2 ms | 384 KB |
00_small126.txt | AC | 2 ms | 384 KB |
00_small127.txt | AC | 2 ms | 384 KB |
00_small128.txt | AC | 2 ms | 384 KB |
00_small129.txt | AC | 2 ms | 384 KB |
00_small130.txt | AC | 2 ms | 384 KB |
00_small131.txt | AC | 2 ms | 384 KB |
00_small132.txt | AC | 2 ms | 384 KB |
00_small133.txt | AC | 2 ms | 384 KB |
00_small134.txt | AC | 2 ms | 384 KB |
00_small135.txt | AC | 2 ms | 384 KB |
00_small136.txt | AC | 2 ms | 384 KB |
00_small137.txt | AC | 2 ms | 384 KB |
00_small138.txt | AC | 2 ms | 384 KB |
00_small139.txt | AC | 2 ms | 384 KB |
00_small140.txt | AC | 2 ms | 384 KB |
00_small141.txt | AC | 2 ms | 384 KB |
00_small142.txt | AC | 2 ms | 384 KB |
00_small143.txt | AC | 2 ms | 384 KB |
00_small144.txt | AC | 2 ms | 384 KB |
00_small145.txt | AC | 2 ms | 384 KB |
00_small146.txt | AC | 2 ms | 384 KB |
00_small147.txt | AC | 2 ms | 384 KB |
00_small148.txt | AC | 2 ms | 384 KB |
00_small149.txt | AC | 2 ms | 384 KB |
00_small150.txt | AC | 2 ms | 384 KB |
00_small151.txt | AC | 2 ms | 384 KB |
00_small152.txt | AC | 2 ms | 384 KB |
00_small153.txt | AC | 2 ms | 384 KB |
00_small154.txt | AC | 2 ms | 384 KB |
00_small155.txt | AC | 2 ms | 384 KB |
00_small156.txt | AC | 2 ms | 384 KB |
00_small157.txt | AC | 2 ms | 384 KB |
00_small158.txt | AC | 2 ms | 384 KB |
01_large100.txt | AC | 2 ms | 384 KB |
01_large101.txt | AC | 2 ms | 384 KB |
01_large102.txt | AC | 2 ms | 384 KB |
01_large103.txt | AC | 2 ms | 512 KB |
01_large104.txt | AC | 2 ms | 512 KB |
01_large105.txt | AC | 2 ms | 512 KB |
01_large106.txt | AC | 2 ms | 512 KB |
01_large107.txt | AC | 2 ms | 512 KB |
01_large108.txt | AC | 27 ms | 768 KB |
01_large1325.txt | AC | 6 ms | 640 KB |
01_large1327.txt | AC | 33 ms | 768 KB |
01_large1330.txt | AC | 40 ms | 768 KB |
01_large1339.txt | AC | 5 ms | 640 KB |
01_large1343.txt | AC | 38 ms | 896 KB |
01_large1355.txt | AC | 34 ms | 768 KB |
01_large1366.txt | AC | 11 ms | 640 KB |
01_large1367.txt | AC | 5 ms | 640 KB |
01_large1374.txt | AC | 9 ms | 640 KB |
01_large1380.txt | AC | 9 ms | 640 KB |
01_large1388.txt | AC | 15 ms | 640 KB |
01_large1395.txt | AC | 6 ms | 640 KB |
01_large1396.txt | AC | 35 ms | 768 KB |
01_large1400.txt | AC | 38 ms | 768 KB |
01_large1402.txt | AC | 14 ms | 640 KB |
01_large1405.txt | AC | 4 ms | 640 KB |
01_large1409.txt | AC | 5 ms | 640 KB |
01_large1413.txt | AC | 36 ms | 768 KB |
01_large1417.txt | AC | 46 ms | 768 KB |
01_large1423.txt | AC | 5 ms | 640 KB |
01_large1430.txt | AC | 13 ms | 640 KB |
01_large1437.txt | AC | 5 ms | 640 KB |
01_large1438.txt | AC | 37 ms | 768 KB |
01_large1442.txt | AC | 43 ms | 768 KB |
01_large1450.txt | AC | 12 ms | 640 KB |
01_large1459.txt | AC | 41 ms | 768 KB |
01_large1464.txt | AC | 12 ms | 640 KB |
01_large1472.txt | AC | 9 ms | 640 KB |
01_large1478.txt | AC | 15 ms | 640 KB |
01_large1480.txt | AC | 42 ms | 768 KB |
01_large1486.txt | AC | 8 ms | 640 KB |
01_large1492.txt | AC | 11 ms | 640 KB |
01_large1500.txt | AC | 11 ms | 640 KB |
01_large1501.txt | AC | 29 ms | 768 KB |
01_large1502.txt | AC | 4 ms | 640 KB |
01_large1506.txt | AC | 9 ms | 640 KB |
01_large157.txt | AC | 30 ms | 768 KB |
01_large207.txt | AC | 38 ms | 768 KB |
01_large507.txt | AC | 44 ms | 768 KB |
01_large577.txt | AC | 33 ms | 768 KB |
01_large591.txt | AC | 35 ms | 768 KB |
01_large893.txt | AC | 36 ms | 768 KB |
01_manual_L00.txt | AC | 3 ms | 512 KB |
01_manual_L01.txt | AC | 3 ms | 512 KB |