Submission #776967

#TimeUsernameProblemLanguageResultExecution timeMemory
776967blacktulipSajam (COCI18_sajam)C++17
90 / 90
17 ms6324 KiB
#include <bits/stdc++.h> using namespace std; typedef long long lo; #define fi first #define se second #define endl "\n" #define pb push_back #define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define FOR for(int i=1;i<=n;i++) #define mid ((start+end)/2) #define ort ((bas+son)/2) const lo inf = 1000000000; const lo li = 1005; const lo mod = 1000000007; int n,m,a[li][li],k,flag,t,acik[li],tut[li]; int cev; string s[li]; vector<int> v; int main(void){ fio(); cin>>n>>k; FOR cin>>s[i]; //~ if(k>(n+1)/2){cout<<"DA\n";return 0;} FOR{ for(int j=0;j<n;j++){ if(s[i][j]=='o')a[i][j]=1; } } //~ for(int ii=1;ii<=n;ii++){ int ii=1; cev=0; for(int i=1;i<=n;i++){ if(i==ii)continue; int say=0; for(int j=0;j<n;j++){ if((a[ii][j]^a[i][j]))say++; } tut[i]=say; cev+=min(say,n-say); //~ cout<<i<<" ()() "<<cev<<endl; } v.clear(); for(int j=0;j<n;j++){ int yes=0; for(int i=1;i<=n;i++){ if(i==ii)continue; if(a[ii][j]!=a[i][j]){ if(tut[i]>=n-tut[i])yes--; else yes++; } else{ if(tut[i]>n-tut[i])yes++; else yes--; } } v.pb(yes); } sort(v.begin(),v.end()); reverse(v.begin(),v.end()); int sayac=0,say2=0; if(cev<=k){cout<<"DA\n";return 0;} for(auto go:v){ sayac++; say2+=go; //~ cout<<say2<<" :: "<<sayac<<" :: "<<cev<<endl; if(cev-say2<=k-sayac){cout<<"DA\n";return 0;} } //~ } cout<<"NE\n"; return 0; cev=k+1; FOR{ v.clear(); for(int j=0;j<n;j++){ if(s[i][j]=='o')v.pb(acik[j]); else v.pb(n-acik[j]); } sort(v.begin(),v.end()); if(n%2){ int cur=0; for(auto go:v)cur+=abs(go-v[n/2]); //~ cout<<cur<<" AAA "<<cev<<endl; cev=min(cev,cur); } else{ int cur=0; for(auto go:v)cur+=abs(go-v[n/2]); //~ cout<<cur<<" BBB "<<cev<<endl; cev=min(cev,cur); cur=0; for(auto go:v)cur+=abs(go-v[n/2-1]); //~ cout<<cur<<" CCC "<<cev<<endl; cev=min(cev,cur); } } if(cev>k)cout<<"NE\n"; else cout<<"DA\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...