| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 582085 | TimDee | Colouring a rectangle (eJOI19_colouring) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define paiu return
#define moment 0;
#define int long long
#define ll long long
#define forn(i,x) for (int i=0; i<x; i++)
#define vi(a,n) vector<int> a(n,0)
//cringe define
#define vii(a,n) vi(a,n); forn(i,n) cin>>a[i];
vector<int> ___makeprefsum(vector<int>&a) {
int n=a.size();
vi(pr,n+1);
forn(i,n) pr[i+1]=pr[i]+a[i];
return pr;
}
#define prefsum(pr,a) vector<int> pr=___makeprefsum(a);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb(x) push_back(x)
#define pf pop_front();
#define last(c) c[c.size()-1]
#define f first
#define s second
#define pi pair<int, int>
#define mp(x,y) make_pair(x, y)
const ll mod = 1000000007;
const double ppi = acos(0) * 2;
//const int maxn = 3e5+1;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
const ll mmod = 998244353;
struct node {
int sz=0,cost=0;
vector<vector<int>> a;
vector<int> used;
};
vector<node> v;
int n,m;
void bruteforce(vector<int>&a, vector<int>&b, node N, int i) {
if (i==n+m-1+n+m-1) {
v.pb(N);
return;
}
bruteforce(a,b,N,i+1);
N.used.pb(i);
if (i>=n+m-1) {
//work with B
N.cost+=b[i-n-m+1];
if (i-n-m+1>=n) {
//work with Bottom
int y=i-n-m+1-n+1;
int x=n-1;
while (x>=0 && y<m) {
N.sz+=1-N.a[x][y];
N.a[x][y]=1;
x--,y++;
}
} else {
//work with Left
int y=0;
int x=i-n-m+1;
while (x>=0 && y<m) {
N.sz+=1-N.a[x][y];
N.a[x][y]=1;
x--,y++;
}
}
} else {
//work with A
N.cost+=a[i];
if (i<m) {
//work with Top
int y=m-1-i;
int x=0;
while (x<n && y<m) {
N.sz+=1-N.a[x][y];
N.a[x][y]=1;
x++,y++;
}
} else {
//work with Left
int y=0;
int x=i-m+1;
while (x<n && y<m) {
N.sz+=1-N.a[x][y];
N.a[x][y]=1;
x++,y++;
}
}
}
bruteforce(a,b,N,i+1);
}
void solve() {
cin>>n>>m;
vii(md,m+n-1);
vii(pd,m+n-1);
if (m==1) {
int ans=0;
forn(i,n) {
ans+=min(md[i],pd[i])
}
cout<<ans;
return;
}
node zero;
zero.a.resize(n);
forn(i,n) zero.a[i].assign(m,0);
bruteforce(md,pd,zero,0);
int ans=linf;
forn(i,v.size()) {
//cout<<v[i].sz<<' '<<v[i].cost<<'\n';
//forn(j,n) {
// forn(k,m) cout<<v[i].a[j][k]<<' ';
// cout<<'\n';
//}
//cout<<'\n';
}
forn(i,v.size()) if (v[i].sz==n*m) {
if (ans>v[i].cost) {
ans=v[i].cost;
//forn(j,n) {
// forn(k,m) cout<<v[i].a[j][k]<<' ';
// cout<<'\n';
//}
//cout<<"! ";
//forn(j,v[i].used.size()) cout<<v[i].used[j]<<' '; cout<<'\n';
//cout<<'\n';
}
}
cout<<ans;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//init_primes();
int t=1;
//cin>>t;
while(t--) solve();
paiu moment
}