oj.uz

Submission #1100182

# Submission time Handle Problem Language Result Execution time Memory
1100182 2024-10-13T08:49:07 Z _rain_ Selotejp (COCI20_selotejp) C++14
35 / 110
 1000 ms 25172 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ll long long 
#define BIT(mask,x) ((mask)>>(x)&(1))
#define MASK(x) ((ll)(1)<<(x))
#define all(datastructure) datastructure.begin(),datastructure.end()
void compress(vector<int>&x){
	x.resize(unique(all(x))-x.begin());
}
template <class T1 , class T2>
	bool minU(T1 &a, T2 b){
		if (a>b) return a = b , true;
		return false;
	}
template <class T1 , class T2>
	bool maxU(T1 &a, T2 b){
		if (a<b) return a = b,true;
		return false;
	}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int Rand(int l , int r){
	return uniform_int_distribution<int> (l,r)(rng);
}

const int maxn = 1000;
const int maxm = 10;
int numrow,numcol;
bool c[maxn+2][maxm+2];
int a[maxn+2][MASK(maxm)];
int dp[maxn+2][MASK(maxm)];
int f[maxn+2][MASK(maxm)];
int un[maxn+2][MASK(maxm)];

bool ok(int id , int mask){
	for (int i = 0; i < numcol; ++i){
		if (BIT(mask,i) && c[id][i]==false) return false;
	}
	return true;
}
void calc(int id , int mask){
	int mask2 = mask;
	int ans = 0 , cnt = 0 , ngang = 0;
	for (int i = 0; i < numcol; ++i){
		if (BIT(mask,i)){
			if (c[id-1][i]==0){
				mask2^=MASK(i);
				++cnt;
			}
			ans += ngang;
			ngang = 0;
		}
		else {
			if (c[id][i]==false){
				ans += ngang;
				ngang = 0;
			}
			else 
			if (i==0||BIT(mask,i-1)||c[id][i-1]==false) ngang = 1;
		}
	}
	ans += ngang ;
	int res = (int)1e9+7;
	for (int mask2 = 0; mask2 < MASK(numcol); ++mask2){
		dp[id][mask] = min(dp[id][mask] , dp[id-1][mask2] + ans + (__builtin_popcount(mask)) - (__builtin_popcount(mask2&mask)));
	}
}


int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	#define name "main"
	if (fopen(name".inp","r")){
		freopen(name".inp","r",stdin);
		freopen(name".ans","w",stdout);
	}
	cin >> numrow >> numcol;
	for (int i = 1; i <= numrow; ++i){
		for (int j = 0; j < numcol; ++j){
			char x; cin >> x;
			if (x=='#') c[i][j] = true; else c[i][j] = false;
		}
	}
	memset(dp,0x3f,sizeof dp);
	memset(f,0x3f,sizeof f);
	memset(un,0x3f,sizeof un);
	for (int i = 0; i < numcol; ++i) c[0][i] = false;
	for (int mask = 0; mask < MASK(numcol); ++mask) dp[0][mask] = __builtin_popcount(mask);
	for (int i = 1; i <= numrow;++i){
		for (int mask = 0; mask < MASK(numrow); ++mask)
			if (ok(i,mask))
				calc(i,mask);
	}
	int ans = numrow*numcol;
	for (int mask = 0; mask < MASK(numcol); ++mask){
		ans = min(ans,dp[numrow][mask]);
	}
	cout << ans;
}

Compilation message

Main.cpp: In function 'void calc(long long int, long long int)':
Main.cpp:63:6: warning: unused variable 'res' [-Wunused-variable]
   63 |  int res = (int)1e9+7;
      |      ^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:75:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   freopen(name".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   freopen(name".ans","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 ms 25172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25172 KB Output is correct
2 Correct 10 ms 25172 KB Output is correct
3 Correct 4 ms 25172 KB Output is correct
4 Correct 12 ms 25172 KB Output is correct
5 Correct 4 ms 25172 KB Output is correct
6 Correct 4 ms 25172 KB Output is correct
7 Correct 6 ms 25172 KB Output is correct
8 Correct 8 ms 25172 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 ms 25172 KB Time limit exceeded
2 Halted 0 ms 0 KB -