| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 956195 |
2024-04-01T09:47:04 Z |
kigash |
Tents (JOI18_tents) |
C++17 |
|
50 ms |
8796 KB |
#include "bits/stdc++.h"
using namespace std;
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
ll binmul(ll a, ll b, ll c) { ll res = 0; while(b) { if(b&1) (res += a) %= c; (a += a) %= c; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll c) { ll res = 1; while(b) { if(b&1) (res *= a) %= c; (a *= a) %= c; b >>= 1; } return res; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll inf = 1e18+7, MX = LLONG_MAX, MN = LLONG_MIN;
const ll mod = 1e9+7, N = 2e3+5;
ll dp[N][2][N];
string s[N];
void yesyesyes() {
ll n, m;
cin>>n>>m;
for(ll i=0; i<n; i++) cin>>s[i];
for(ll mask=0; mask<(1<<m); mask++) dp[0][0][mask] = (s[0][0]=='#');
for(ll i=0; i<n; i++) {
for(ll j=0; j<m; j++) {
if(!i && !j) continue;
for(ll mask=0; mask<(1<<m); mask++) {
ll mn = inf;
if(s[i][j]=='.') {
if(j) mn = min({mn, dp[i][(j-1)%2][mask], dp[i][(j-1)%2][mask^(1<<j)]});
else mn = min({mn, dp[i-1][(m-1)%2][mask], dp[i-1][(m-1)%2][mask^(1<<j)]});
dp[i][j%2][mask] = mn;
continue;
}
if(mask&(1<<j)) {
ll add = 1;
if(j && s[i][j-1]=='#' && (mask&(1<<(j-1)))>0) add = 0;
if(j) mn = min({mn, dp[i][(j-1)%2][mask]+add, dp[i][(j-1)%2][mask^(1<<j)]+add});
else mn = min({mn, dp[i-1][(m-1)%2][mask]+1, dp[i-1][(m-1)%2][mask^(1<<j)]+1});
dp[i][j%2][mask] = mn;
}
else {
if(i && s[i-1][j]=='#') {
if(j) mn = min(mn, dp[i][(j-1)%2][mask]);
else mn = min(mn, dp[i-1][(m-1)%2][mask]);
}
if(j) mn = min({mn, dp[i][(j-1)%2][mask]+1, dp[i][(j-1)%2][mask^(1<<j)]+1});
else mn = min({mn, dp[i-1][(m-1)%2][mask]+1, dp[i-1][(m-1)%2][mask^(1<<j)]+1});
dp[i][j%2][mask] = mn;
}
}
}
}
ll ans = MX;
for(ll mask=0; mask<(1<<m); mask++) ans = min(ans, dp[n-1][(m-1)%2][mask]);
cout<<ans<<"\n";
return;
}
signed main(/*Kigash Amir*/) {
// freopen("");
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll tt = 1;
// cin>>tt;
for(ll i=1; i<=tt; i++) {
yesyesyes();
}
}
Compilation message
tents.cpp: In function 'void freopen(std::string)':
tents.cpp:17:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tents.cpp:17:73: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
