Submission #1209706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209706		garam1732	여왕벌 (KOI15_queen)	C++20	100 / 100	2526 ms	184896 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*10;
const ll MOD = 998244353;
const ll INF = 1e16;

const int MAXM = 770;
string info[MAXM][MAXM];

#define Input vector<vector<int> >
#define Output vector<vector<pi> >

int res[MAXM][MAXM];

void init(Input& v, int len) {
    v.resize(len+1); for(auto &x:v) x.resize(len+1);
} void init(Output& v, int len) {
    v.resize(len+1); for(auto &x:v) x.resize(len+1);
}

//int nn;

void dnc(int sx, int ex, int sy, int ey, Input& v0, Output& dp0) {//++nn;
    int L = ex-sx+ey-sy+1;
    // cout<<sx<<bl<<ex<<bl<<sy<<bl<<ey<<" mp : "<<endl;
    // for(int i=0; i<=L; i++){ for(int j=0; j<=L; j++) {            
    //         cout<<v0[i][j]<<bl;
    //     } cout<<endl;}
    
    
    if(sx==ex || sy==ey) {
        for(int i=0; i<=L; i++) for(int j=0; j<=L; j++) {
            dp0[i][j] = pi(i,j);
        } return;
    }
    if(sx+1==ex && sy+1==ey) {
        for(int i=0; i<=L; i++) for(int j=0; j<=L; j++) {
            if(!v0[i][j]) continue;

            int idx; int cnt = v0[i][j];
            if(i==3) idx=0;
            else if(i==2 && j==0) idx=1;
            else if(i==2) idx=2;
            else if(i==1 && j==0) idx=4;
            else if(i==1 && j==2) idx=8;
            else if(i==1) idx=5;
            else if(j==0) idx=13;
            else if(j==1) idx=14;
            else if(j==2) idx=17;
            else idx=26;

            int col;
            if(info[ex][ey][idx] == 'L') col=idx/9;
            else if(info[ex][ey][idx] == 'D') col=idx/3%3;
            else col=idx%3;

            res[ex][ey] += col*cnt;

            vector<int> y = {0,0,0};
            y[col]++; y[idx/9]++; y[idx%3]++;
            dp0[i][j] = pi(y[0], y[2]);
        } 

    //     cout<<sx<<bl<<ex<<bl<<sy<<bl<<ey<<" dp : "<<endl;
    // for(auto [x,y] : dp[sz]) {            
    //         cout<<x.a<<bl<<x.b<<bl<<x.c<<bl<<y.a<<bl<<y.b<<bl<<y.c<<endl;
    //     } 

        return;
    }

    int mx=sx+ex>>1, my=sy+ey>>1;
    Input v[4]; Output dp[4], w[4];
    int len[4] = {mx-sx+my-sy+1, mx-sx+ey-my+1, ex-mx+my-sy+1, ex-mx+ey-my+1};

    for(int i=0; i<4; i++) {
        init(v[i], len[i]);
        init(dp[i], len[i]);
        init(w[i], L);
    }

    for(int i=0; i<=L; i++) for(int j=0; j<=L; j++) {
        if(!v0[i][j]) continue;

        int tot = mx-sx+my-sy+1; int cnt = v0[i][j];
        int a = min(tot, max(0, i-(ex-mx)));
        int c = min(tot, max(0, j-(ey-my)));
        //int b = tot-a-c;
        v[0][a][c] += cnt;
        w[0][i][j] = pi(a,c);
    }
    dnc(sx, mx, sy, my, v[0], dp[0]);

    for(int i=0; i<=L; i++) for(int j=0; j<=L; j++) {
        if(!v0[i][j]) continue;

        int tot1 = mx-sx+1, tot2 = ey-my; int cnt = v0[i][j];
        int a = min(tot1, max(0, dp[0][w[0][i][j].ff][w[0][i][j].ss].ff-(my-sy))) + min(tot2, max(0, i-(ex-sx+my-sy+1)));
        int c = min(tot1, dp[0][w[0][i][j].ff][w[0][i][j].ss].ss) + min(tot2, j);
        //int b = tot1+tot2-a-c;
        v[1][a][c] += cnt;
        w[1][i][j] = pi(a,c);
    }
    dnc(sx, mx, my, ey, v[1], dp[1]);

    for(int i=0; i<=L; i++) for(int j=0; j<=L; j++) {
        if(!v0[i][j]) continue;

        int tot1 = ex-mx, tot2 = my-sy+1; int cnt = v0[i][j];
        int a = min(tot1, i) + min(tot2, dp[0][w[0][i][j].ff][w[0][i][j].ss].ff);
        int c = min(tot1, max(0, j-(ey-sy+mx-sx+1))) + min(tot2, max(0, dp[0][w[0][i][j].ff][w[0][i][j].ss].ss-(mx-sx)));
        //int b = tot1+tot2-a-c;
        v[2][a][c] += cnt;
        w[2][i][j] = pi(a,c);
    }
    dnc(mx, ex, sy, my, v[2], dp[2]);

    for(int i=0; i<=L; i++) for(int j=0; j<=L; j++) {
        if(!v0[i][j]) continue;

        int tot1 = ex-mx+1, tot2 = ey-my; int cnt = v0[i][j];
        int a = min(tot1, max(0, dp[2][w[2][i][j].ff][w[2][i][j].ss].ff-(my-sy))) + min(tot2, max(0, dp[1][w[1][i][j].ff][w[1][i][j].ss].ff-1));
        int c = min(tot1, dp[2][w[2][i][j].ff][w[2][i][j].ss].ss) + min(tot2, max(0, dp[1][w[1][i][j].ff][w[1][i][j].ss].ss-(mx-sx)));
        //int b = tot1+tot2-a-c;
        v[3][a][c] += cnt;
        w[3][i][j] = pi(a,c);
    }
    dnc(mx, ex, my, ey, v[3], dp[3]);

    for(int i=0; i<=L; i++) for(int j=0; j<=L; j++) {
        if(!v0[i][j]) continue;

        int tot1 = my-sy, tot2 = mx-sx, tot3 = ex-mx+ey-my+1; 
        int a = min(tot1, dp[2][w[2][i][j].ff][w[2][i][j].ss].ff) + min(tot2, max(0, dp[1][w[1][i][j].ff][w[1][i][j].ss].ff-(ey-my+1))) + dp[3][w[3][i][j].ff][w[3][i][j].ss].ff;
        int c = min(tot1, max(0, dp[2][w[2][i][j].ff][w[2][i][j].ss].ss-(ex-mx+1))) + min(tot2, dp[1][w[1][i][j].ff][w[1][i][j].ss].ss) + dp[3][w[3][i][j].ff][w[3][i][j].ss].ss;
        //int b = tot1+tot2+tot3-a-c;
        dp0[i][j] = pi(a,c);
    }

    // for(int x=0; x<4; x++) {
    //     mp[x].clear(); dp[x].clear(); w[x].clear();
    // }

    // cout<<sx<<bl<<ex<<bl<<sy<<bl<<ey<<" dp : "<<endl;
    // for(auto [x,y] : dp[sz-1]) {            
    //         cout<<x.a<<bl<<x.b<<bl<<x.c<<bl<<y.a<<bl<<y.b<<bl<<y.c<<endl;
    //     } 
}

vector<pi> line;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int m, n; cin>>m>>n;
    for(int i=1; i<m; i++) {
        for(int j=1; j<m; j++) {
            cin >> info[i][j];
        }
    }

    for(int i=m-1; i; i--) line.push_back(pi(i, 0));
    for(int j=0; j<m; j++) line.push_back(pi(0, j));

    Input v; Output dp; int L = 2*m-1;
    init(v, L); init(dp, L);

    for(int i=0; i<n; i++) {
        int a,b,c; cin>>a>>b>>c;
        v[a][c]++;

        for(auto [x,y] : line) {
            if(a) a--;
            else if(b) {
                b--; res[x][y]+=1;
            } else {
                c--; res[x][y]+=2;
            }
        }
    }

    dnc(0, m-1, 0, m-1, v, dp);

    for(int i=0; i<m; i++) {
        for(int j=0; j<m; j++) cout<<res[i][j]+1<<bl;
        cout<<endl;
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 34 / 34
• Subtask 4: 32 / 32