oj.uz

Submission #236223

# Submission time Handle Problem Language Result Execution time Memory
236223 2020-05-31T16:31:42 Z Aldas25 Coins (LMIO19_monetos) C++14
100 / 100
 484 ms 69112 KB 
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;

int t, n, k1, k2;

bool grid[310][310];
bool nGrid[310][310];
bool ans[310][310];
int bst;

int checkGrid () {
    int ret = 0;
    FOR(i, 1, n) FOR(j, 1, n)
        if (grid[i][j] != nGrid[i][j]) ret++;
    return (ret/2);
}

void setGrid() {
    int nBst = checkGrid();
    if (nBst < bst) {
        bst = nBst;
        FOR(i, 1, n) FOR(j, 1, n) ans[i][j] = nGrid[i][j];
    }
}

void printAns (){
    //cout << "  bst=" << bst << endl;
    FOR(i,1  ,n) {
        FOR(j, 1, n) cout << ans[i][j] << " ";
        cout << "\n";
    }
}

void checkRectangle (int x, int y) {
    FOR(i, 1, n) FOR(j, 1, n) nGrid[i][j] = 0;
    FOR(i, n-x+1, n) FOR(j, n-y+1, n) nGrid[i][j] = 1;
    setGrid();
}

int dp[110][110][65*65];
int p[110][110][65*65];
int stulp[110][115];
int cnt[110][110];
bool temp[110][110];
int orN;
void solveDP() {

    orN = n;
    int kx = 5;
    FOR(i, 1, n) FOR(j, 1, n) {
        int nI = (i+kx-1)/kx;
        int nJ = (j+kx-1)/kx;
        if (orN <= 50) nI = i, nJ = j;
        cnt[nI][nJ] += !(grid[i][j]);
    }

    if (orN > 50) n /= kx;

    //FOR(i, 1, n) FOR(j, 1, n) cerr << "  cnt (" << i << ", " << j << ") = " << cnt[i][j] << endl;

    FOR(j, 1, n) for (int i = n; i > 0; i--) stulp[i][j] = stulp[i+1][j] + cnt[i][j];


    FOR(i, 0, n) FOR(j, 0, n) FOR(k, 0, n*n/2) dp[i][j][k] = 500*500;
    dp[0][0][0] = 0;

    int mnAns = 500*500;
    int curJ = 0;

    FOR(j, 1, n) FOR(i, 0, n) FOR(k, 0, n*n/2) {
        FOR(prJ, 0, n) {
            if (prJ > i) break;
            int prS = k-i;
            if (dp[j][i][k] > dp[j-1][prJ][prS] + stulp[n-i+1][j]) {
                dp[j][i][k] = dp[j-1][prJ][prS] + stulp[n-i+1][j];
                p[j][i][k] = prJ;
            }
        }
        //if (i == n && k == n*n/2 && dp) mnAns = min(mnAns, dp[j][i][k]);
    }



    FOR(j, 0, n) {
        if (dp[n][j][n*n/2] < mnAns) {
            mnAns = dp[n][j][n*n/2];
            curJ = j;
        }
    }

    int curS = n*n/2;
    for (int j = n; j > 0; j--) {
        FOR(i, 1, n) temp[i][j] = 0;
        FOR(i, n-curJ+1, n) temp[i][j] = 1;
        int nSum = curS - curJ;
        curJ = p[j][curJ][curS];
        curS = nSum;
    }

    //FOR(i, 1, n) FOR(j, 1, n) cerr << " temp[" << i << "][" << j << "] = " << temp[i][j] << endl;

    FOR(i, 1, n) FOR(j, 1,n) {
        if (orN> 50) FOR(di, i*kx - kx+1, i*kx) FOR(dj, j*kx - kx+1, j*kx) ans[di][dj] = temp[i][j];
        else ans[i][j] = temp[i][j];
    }

    if (orN > 50) n *= kx;

}

int main()
{
    FAST_IO;

    //freopen("monetos-vyr.03.in","r",stdin);
	//freopen("monetos-vyr.03.out","w",stdout);

    cin >> t >> n >> k1 >> k2;
    FOR(i, 1, n) FOR(j, 1, n) cin >> grid[i][j];

    //if (n <= 50) {
        solveDP();
    //bst = checkGrid();
        printAns();
   //     return 0;
   // }

    /*FOR(i, 1, n) {
        FOR(j, 1, n/2) nGrid[i][j] = ans[i][j] = 0;
        FOR(j, n/2+1, n) nGrid[i][j] = ans[i][j] = 1;
    }
    setGrid();
    //bst = checkGrid();

    FOR(i, 1, n/2) FOR(j, 1, n) nGrid[i][j] = 0;
    FOR(i, n/2+1, n) FOR(j, 1, n) nGrid[i][j] = 1;
    setGrid();

    FOR(i, 1, n) {
        int rp = n-i+1;
        if (i > n/2) rp--;
        FOR(j, 1, rp) nGrid[i][j] = 0;
        FOR(j, rp+1, n) nGrid[i][j] = 1;
    }
    setGrid();

    FOR(i, 1, n) {
        if ((n*n/2)%i == 0) checkRectangle(i, (n*n/2)/i);
    }

    printAns();
*/
    return 0;
}

Compilation message

monetos.cpp:1:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB K = 17
2 Correct 203 ms 39800 KB K = 576
3 Correct 458 ms 69076 KB K = 18657
4 Correct 466 ms 68856 KB K = 21839
5 Correct 441 ms 69112 KB K = 17169
6 Correct 456 ms 68984 KB K = 20873
7 Correct 484 ms 69112 KB K = 21477
8 Correct 443 ms 68856 KB K = 19614
9 Correct 435 ms 68856 KB K = 20777
10 Correct 455 ms 68984 KB K = 20150