結果

問題 No.1948 足し算するだけのパズルゲーム(1)
コンテスト
ユーザー erbowl
提出日時 2022-08-07 21:27:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,145 bytes
コンパイル時間 1,984 ms
コンパイル使用メモリ 200,112 KB
最終ジャッジ日時 2025-01-30 19:18:40
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

typedef long long ll;
typedef long double ld;
#include <bits/stdc++.h>
using namespace std;
#define int long long

typedef tuple<ll,ll,ll> tll;

signed main(){
    ll h,w,y,x;
    std::cin >> h>>w;
    vector<vector<ll>> a(h,vector<ll>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            std::cin >> a[i][j];
        }
    }
    vector<vector<ll>> b1(h,vector<ll>(w,-1));
    vector<vector<ll>> b2(h,vector<ll>(w,-1));
    b1[0][0]=a[0][0];
    for (int ii = 0; ii < w; ii++) {
        ll x,y;
        x = ii;
        y = 0;
        while(0<=x&&y<h){
            if(b1[y][x]!=-1){
                if(y+1<h){
                    if(a[y+1][x]<b1[y][x]){
                        b1[y+1][x] = max(b1[y+1][x],b1[y][x]+a[y+1][x]);
                    }else{
                        b2[y+1][x] = max(b1[y+1][x],b1[y][x]);
                    }
                }
                if(x+1<w){
                    if(a[y][x+1]<b1[y][x]){
                        b1[y][x+1] = max(b1[y][x+1],b1[y][x]+a[y][x+1]);
                    }else{
                        b2[y][x+1] = max(b1[y][x+1],b1[y][x]);
                    }
                }
            }
            if(b2[y][x]!=-1){
                if(y+1<h){
                    if(a[y+1][x]<b2[y][x]){
                        b2[y+1][x] = max(b2[y+1][x],b2[y][x]+a[y+1][x]);
                    }
                }
                if(x+1<w){
                    if(a[y][x+1]<b2[y][x]){
                        b2[y][x+1] = max(b2[y][x+1],b2[y][x]+a[y][x+1]);
                    }
                }
            }
            // std::cout << x<<" "<<y<<" "<<b1[y][x]<<" "<<b2[y][x] << std::endl;
            x--;
            y++;
        }
    }
    for (int ii = 1; ii < h; ii++) {
        ll x,y;
        x = w-1;
        y = ii;
        while(0<=x&&y<h){
            if(b1[y][x]!=-1){
                if(y+1<h){
                    if(a[y+1][x]<b1[y][x]){
                        b1[y+1][x] = max(b1[y+1][x],b1[y][x]+a[y+1][x]);
                    }else{
                        b2[y+1][x] = max(b1[y+1][x],b1[y][x]);
                    }
                }
                if(x+1<w){
                    if(a[y][x+1]<b1[y][x]){
                        b1[y][x+1] = max(b1[y][x+1],b1[y][x]+a[y][x+1]);
                    }else{
                        b2[y][x+1] = max(b1[y][x+1],b1[y][x]);
                    }
                }
            }
            if(b2[y][x]!=-1){
                if(y+1<h){
                    if(a[y+1][x]<b2[y][x]){
                        b2[y+1][x] = max(b2[y+1][x],b2[y][x]+a[y+1][x]);
                    }
                }
                if(x+1<w){
                    if(a[y][x+1]<b2[y][x]){
                        b2[y][x+1] = max(b2[y][x+1],b2[y][x]+a[y][x+1]);
                    }
                }
            }
            // std::cout << x<<" "<<y<<" "<<b1[y][x]<<" "<<b2[y][x] << std::endl;
            x--;
            y++;
        }
    }
    if((b1[h-1][w-1]!=-1)||(b2[h-1][w-1]!=-1&&b2[h-1][w-1]>a[h-1][w-1])){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
}
0