Submission #595482

#TimeUsernameProblemLanguageResultExecution timeMemory
595482AdamGSCoins (LMIO19_monetos)C++17
99.97 / 100
120 ms146104 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=307, INF=1e9+7; int T[LIM][LIM], tmp[LIM][LIM], pref[LIM], wynik[LIM][LIM]; pair<int,int>dp[80][80][80*40]; vector<int>V; bool zmn; int n; void solve() { rep(i, n+1) rep(j, n*n/2) dp[0][i][j+1]={INF, n}; rep(i, n) { rep(j, n) pref[j+1]=T[i][j]+pref[j]; rep(j, n+1) rep(l, n*n/2+1) dp[i+1][j][l]={INF, n}; rep(j, n+1) rep(l, n*n/2+1-j) dp[i+1][j][l+j]={dp[i][j][l].st+pref[j], j}; for(int j=n-1; j>=0; --j) rep(l, n*n/2+1) dp[i+1][j][l]=min(dp[i+1][j][l], dp[i+1][j+1][l]); } int aktp=0, akts=n*n/2; for(int i=n; i; --i) { aktp=dp[i][aktp][akts].nd; akts-=aktp; V.pb(aktp); } reverse(all(V)); } void skaluj() { rep(i, n) rep(j, n) tmp[i/4][j/4]+=T[i][j]; rep(i, n) rep(j, n) T[i][j]=tmp[i][j]; n/=4; zmn=true; } void wypisz() { rep(i, n) rep(j, n) wynik[i][j]=(j>=V[i]); if(zmn) { rep(u, 8) { bool zmienione=false; rep(i, n) rep(j, n) if((!i || !wynik[i-1][j]) && (!j || !wynik[i][j-1]) && wynik[i][j] && !zmienione) { wynik[i][j]=0; zmienione=true; } if(!zmienione) rep(i, n) rep(j, n) if(wynik[i][j] && !zmienione) { wynik[i][j]=0; zmienione=true; } } } rep(i, n) { rep(j, n) cout << wynik[i][j] << " "; cout << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t, k1, k2; cin >> t >> n >> k1 >> k2; rep(i, n) rep(j, n) cin >> T[i][j]; if(t==1 || t==2) solve(); else { skaluj(); solve(); vector<int>S; rep(i, V.size()) rep(j, 4) S.pb(4*V[i]); V=S; n*=4; } wypisz(); }

Compilation message (stderr)

monetos.cpp: In function 'int main()':
monetos.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
monetos.cpp:67:5: note: in expansion of macro 'rep'
   67 |     rep(i, V.size()) rep(j, 4) S.pb(4*V[i]);
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...