Submission #395139

#	Time	Username	Problem	Language	Result	Execution time	Memory
395139		duality	Wall (CEOI14_wall)	C++11	60 / 100	2138 ms	707324 KiB

wall

#define DEBUG 0

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int grid[400][400],pre[400][401];
int ver[400][401],hor[401][400];
LLI dist[401][401][401],dp[401][401],dp2[401][401];
priority_queue<pair<LLI,pair<int,pii> > > H;
int main() {
    int i,j;
    int N,M;
    scanf("%d %d",&N,&M);
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) scanf("%d",&grid[i][j]),pre[i][j+1] = pre[i][j]+grid[i][j];
    }
    for (i = 0; i < N; i++) {
        for (j = 0; j <= M; j++) scanf("%d",&ver[i][j]);
    }
    for (i = 0; i <= N; i++) {
        for (j = 0; j < M; j++) scanf("%d",&hor[i][j]);
    }

    int k;
    for (i = 0; i <= N; i++) {
        for (j = 0; j <= M; j++) {
            for (k = 0; k <= M; k++) dist[i][j][k] = 1e18;
        }
        for (j = 0; j <= M; j++) {
            dist[i][j][j] = 0;
            H.push(mp(0,mp(i,mp(j,j))));
        }
    }
    while (!H.empty()) {
        LLI d = -H.top().first;
        int r = H.top().second.first;
        int x = H.top().second.second.first;
        int y = H.top().second.second.second;
        H.pop();

        if (x > 0) {
            if (d+hor[r][x-1] < dist[r][x-1][y]) {
                dist[r][x-1][y] = d+hor[r][x-1];
                H.push(mp(-dist[r][x-1][y],mp(r,mp(x-1,y))));
            }
        }
        if (x < M) {
            if (d+hor[r][x] < dist[r][x+1][y]) {
                dist[r][x+1][y] = d+hor[r][x];
                H.push(mp(-dist[r][x+1][y],mp(r,mp(x+1,y))));
            }
        }
        if (y > 0) {
            if (d+hor[r][y-1] < dist[r][x][y-1]) {
                dist[r][x][y-1] = d+hor[r][y-1];
                H.push(mp(-dist[r][x][y-1],mp(r,mp(x,y-1))));
            }
        }
        if (y < M) {
            if (d+hor[r][y] < dist[r][x][y+1]) {
                dist[r][x][y+1] = d+hor[r][y];
                H.push(mp(-dist[r][x][y+1],mp(r,mp(x,y+1))));
            }
        }
        if ((r > 0) && (pre[r-1][max(x,y)]-pre[r-1][min(x,y)] == 0)) {
            if (d+ver[r-1][x]+ver[r-1][y] < dist[r-1][x][y]) {
                dist[r-1][x][y] = d+ver[r-1][x]+ver[r-1][y];
                H.push(mp(-dist[r-1][x][y],mp(r-1,mp(x,y))));
            }
        }
        if ((r < N) && (pre[r][max(x,y)]-pre[r][min(x,y)] == 0)) {
            if (d+ver[r][x]+ver[r][y] < dist[r+1][x][y]) {
                dist[r+1][x][y] = d+ver[r][x]+ver[r][y];
                H.push(mp(-dist[r+1][x][y],mp(r+1,mp(x,y))));
            }
        }
        for (i = 0; i <= M; i++) {
            if (d+dist[r][x][i] < dist[r][y][i]) {
                dist[r][y][i] = d+dist[r][x][i];
                H.push(mp(-dist[r][y][i],mp(r,mp(y,i))));
            }
            if (d+dist[r][y][i] < dist[r][x][i]) {
                dist[r][x][i] = d+dist[r][y][i];
                H.push(mp(-dist[r][x][i],mp(r,mp(x,i))));
            }
        }
    }
    for (i = 0; i <= N; i++) {
        for (j = 0; j <= M; j++) dp[i][j] = dp2[i][j] = 1e18;
    }
    for (i = 0; i <= M; i++) dp[0][i] = dp2[0][i] = dist[0][0][i];
    for (i = 1; i <= N; i++) {
        int l = -1,r = -1;
        for (j = 0; j < M; j++) {
            if (grid[i-1][j]) {
                if (l == -1) l = j;
                r = j;
            }
        }
        for (j = 0; j <= M; j++) {
            if ((r == -1) || (j > r)) dp[i][j] = min(dp[i][j],dp[i-1][j]+ver[i-1][j]);
            if ((l == -1) || (j <= l)) dp2[i][j] = min(dp2[i][j],dp2[i-1][j]+ver[i-1][j]);
        }
        for (j = 0; j <= M; j++) {
            for (k = 0; k <= M; k++) {
                dp[i][k] = min(dp[i][k],dp[i][j]+dist[i][j][k]);
                dp2[i][k] = min(dp2[i][k],dp2[i][j]+dist[i][j][k]);
            }
        }
    }
    for (i = N-1; i >= 0; i--) {
        for (j = 0; j < M; j++) {
            if (grid[i][j]) break;
        }
        if (j < M) break;
    }
    LLI ans = 1e18;
    for (j = 0; j <= M; j++) ans = min(ans,dp[i+1][j]+dp2[i+1][j]);
    printf("%lld\n",ans);

    return 0;
}

Compilation message (stderr)

wall.cpp: In function 'int main()':
wall.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
wall.cpp:67:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         for (j = 0; j < M; j++) scanf("%d",&grid[i][j]),pre[i][j+1] = pre[i][j]+grid[i][j];
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~
wall.cpp:70:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         for (j = 0; j <= M; j++) scanf("%d",&ver[i][j]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:73:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |         for (j = 0; j < M; j++) scanf("%d",&hor[i][j]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40