Submission #518714

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
518714	2022-01-24T13:11:12 Z	inksamurai	Sajam (COCI18_sajam)	C++17	90 / 90	317 ms	1368 KB

sajam

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _343tk3a ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
void print(){cout<<"\n";}
template<class te,class ...ti>
void print(const te&v,const ti&...nv){cout<<v;if(sizeof...(nv)){cout<<" ";print(nv...);}}
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
//e

int main(){
_343tk3a;
	int n,k;
	cin>>n>>k;
	int h,w;
	h=n,w=n;
	vec(bitset<1000>) a(h);
	rep(i,h){
		string s;
		cin>>s;
		rep(j,w){
			a[i][j]=(s[j]=='x');
		}
	}
	bitset<1000> _ie;
	rep(i,n) _ie[i]=1;
	auto af=[&](bitset<1000> _a){
		int res=0;
		rep(i,h){
			res+=min((a[i]^_a).count(),(_ie^a[i]^_a).count());
		}
		return res;
	};
	int res=n+1;
	rep(i,h){
		res=min(res,af(a[i]));
	}
	int i=0;
	rep(j,w){
		a[i][j]=1-a[i][j];
		res=min(res,af(a[i])+1);
		a[i][j]=1-a[i][j];
	}
	print((res<=k?"DA":"NE"),"\n");
//
	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	50 ms	332 KB	Output is correct
3	Correct	69 ms	380 KB	Output is correct
4	Correct	237 ms	448 KB	Output is correct
5	Correct	69 ms	332 KB	Output is correct
6	Correct	26 ms	332 KB	Output is correct
7	Correct	62 ms	376 KB	Output is correct
8	Correct	244 ms	436 KB	Output is correct
9	Correct	13 ms	344 KB	Output is correct
10	Correct	225 ms	460 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	3 ms	204 KB	Output is correct
3	Correct	2 ms	204 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	312 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	3 ms	336 KB	Output is correct
8	Correct	1 ms	208 KB	Output is correct
9	Correct	2 ms	208 KB	Output is correct
10	Correct	2 ms	208 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	416 KB	Output is correct
2	Correct	175 ms	452 KB	Output is correct
3	Correct	115 ms	388 KB	Output is correct
4	Correct	132 ms	332 KB	Output is correct
5	Correct	200 ms	440 KB	Output is correct
6	Correct	80 ms	452 KB	Output is correct
7	Correct	149 ms	412 KB	Output is correct
8	Correct	155 ms	420 KB	Output is correct
9	Correct	42 ms	344 KB	Output is correct
10	Correct	254 ms	460 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	202 ms	332 KB	Output is correct
2	Correct	188 ms	428 KB	Output is correct
3	Correct	110 ms	400 KB	Output is correct
4	Correct	134 ms	404 KB	Output is correct
5	Correct	149 ms	400 KB	Output is correct
6	Correct	237 ms	428 KB	Output is correct
7	Correct	60 ms	376 KB	Output is correct
8	Correct	131 ms	408 KB	Output is correct
9	Correct	142 ms	416 KB	Output is correct
10	Correct	265 ms	460 KB	Output is correct

Subtask #5

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	388 KB	Output is correct
2	Correct	108 ms	332 KB	Output is correct
3	Correct	242 ms	432 KB	Output is correct
4	Correct	77 ms	684 KB	Output is correct
5	Correct	108 ms	820 KB	Output is correct
6	Correct	261 ms	1368 KB	Output is correct
7	Correct	71 ms	584 KB	Output is correct
8	Correct	79 ms	700 KB	Output is correct
9	Correct	82 ms	700 KB	Output is correct
10	Correct	87 ms	680 KB	Output is correct

Subtask #6

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	317 ms	460 KB	Output is correct
2	Correct	253 ms	436 KB	Output is correct
3	Correct	281 ms	456 KB	Output is correct
4	Correct	162 ms	924 KB	Output is correct
5	Correct	140 ms	940 KB	Output is correct
6	Correct	174 ms	956 KB	Output is correct
7	Correct	84 ms	688 KB	Output is correct
8	Correct	205 ms	1084 KB	Output is correct
9	Correct	116 ms	804 KB	Output is correct
10	Correct	255 ms	1328 KB	Output is correct