Submission #403423

#	Time	Username	Problem	Language	Result	Execution time	Memory
403423		lyc	조개 줍기 (KOI17_shell)	C++14	46 / 100	2059 ms	26608 KiB

shell

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
typedef pair<int,int> ii;

const int mxN = 1505;

int N, A[mxN][mxN], B[mxN][mxN], up[mxN][mxN];
long long S;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;

    FOR(i,1,N){
        FOR(j,1,N){
            cin >> A[i][j];

            B[i][j] = max(B[i-1][j], B[i][j-1]) + A[i][j];
            S += B[i][j];
        }
    }

    cout << S << '\n';
    FOR(i,1,N){
        char op;
        int r, c, v;
        cin >> op >> r >> c;
        v = (op == 'U' ? 1 : -1);

        queue<ii> q;
        A[r][c] += v;
        B[r][c] += v;
        S += v;
        q.push(ii(r,c));

        while (!q.empty()) {
            auto u = q.front(); q.pop();
            int dr[] = {0,1};
            int dc[] = {1,0};
            FOR(k,0,1){
                int nr = u.first + dr[k], nc = u.second + dc[k];
                if (nr <= N && nc <= N &&
                        max(B[nr-1][nc], B[nr][nc-1]) + A[nr][nc] != B[nr][nc]) {
                    B[nr][nc] += v;
                    S += v;
                    q.push(ii(nr,nc));
                }
            }
        }

        cout << S << '\n';
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 34 / 34
• Subtask 3: 0 / 54