/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 39ms 796.0 KiB
#3 Accepted 176ms 65.547 MiB
#4 Accepted 144ms 65.711 MiB
#5 Accepted 113ms 65.57 MiB
#6 Accepted 39ms 796.0 KiB
#7 Accepted 41ms 788.0 KiB
#8 Accepted 41ms 840.0 KiB
#9 Accepted 122ms 65.77 MiB
#10 Accepted 123ms 65.574 MiB
#11 Accepted 118ms 65.52 MiB
#12 Accepted 121ms 65.742 MiB
#13 Accepted 120ms 65.879 MiB
#14 Accepted 124ms 65.57 MiB
#15 Accepted 118ms 65.57 MiB
#16 Accepted 124ms 65.582 MiB
#17 Accepted 118ms 65.566 MiB
#18 Accepted 119ms 65.508 MiB
#19 Accepted 117ms 65.551 MiB
#20 Accepted 122ms 65.691 MiB
#21 Accepted 123ms 65.684 MiB
#22 Accepted 122ms 65.699 MiB
#23 Accepted 122ms 65.672 MiB
#24 Accepted 133ms 65.648 MiB
#25 Accepted 124ms 65.664 MiB
#26 Accepted 122ms 65.617 MiB
#27 Accepted 122ms 65.832 MiB
#28 Accepted 122ms 65.863 MiB
#29 Accepted 122ms 65.766 MiB
#30 Accepted 122ms 65.688 MiB
#31 Accepted 122ms 65.539 MiB
#32 Accepted 124ms 65.691 MiB
#33 Accepted 122ms 65.855 MiB
#34 Accepted 130ms 65.52 MiB
#35 Accepted 127ms 65.699 MiB
#36 Accepted 132ms 65.945 MiB
#37 Accepted 142ms 65.535 MiB
#38 Accepted 129ms 65.523 MiB
#39 Accepted 132ms 65.5 MiB
#40 Accepted 130ms 65.641 MiB
#41 Accepted 127ms 65.508 MiB
#42 Accepted 137ms 65.965 MiB
#43 Accepted 131ms 65.516 MiB
#44 Accepted 142ms 65.746 MiB
#45 Accepted 123ms 65.625 MiB
#46 Accepted 122ms 65.664 MiB
#47 Accepted 145ms 65.633 MiB
#48 Accepted 122ms 65.762 MiB
#49 Accepted 124ms 65.656 MiB
#50 Accepted 122ms 65.852 MiB
#51 Accepted 129ms 65.613 MiB
#52 Accepted 119ms 65.734 MiB
#53 Accepted 124ms 65.551 MiB

Code

/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fr freopen("input52.txt","r",stdin);
//ofstream file("output52.txt");
char a[2001][2001];
int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //fr;
    int t;  cin >> t; while(t--)
    {
        ll n,m,x,y; cin >> n >> m >> x >> y;
        vector<vector<pair<ll,ll>>> dp(n+2,vector<pair<ll,ll>>(m+2,{1e18,1e18}));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++) cin >> a[i][j];
        }
        dp[1][1] = {0,0};
        for(int j=2;j<=m;j++) 
        {
            if(a[1][j]=='#') break;
            dp[1][j] = {dp[1][j-1].first + x , dp[1][j-1].first+y};
        }
        for(ll i=2;i<=n;i++)
        {
            for(ll j=1;j<=m;j++)
            {
                if(a[i][j]=='#') continue;
                dp[i][j].first = min(dp[i][j-1].first+x , dp[i-1][j].second+y);
                dp[i][j].second = min(dp[i][j-1].first+y , dp[i-1][j].second+x);
            }
            for(ll j=m;j>=1;j--)
            {
                if(a[i][j]=='#') continue;
                dp[i][j].first = min({dp[i][j].first , dp[i][j+1].first+x, dp[i-1][j].second+y});
                dp[i][j].second = min({dp[i][j].second , dp[i][j+1].first+y , dp[i-1][j].second+x});
            }
        }
        ll ans = min(dp[n][m-1].first , dp[n-1][m].second);
        (ans>=1e18)? cout<<-1<<'\n': cout<<ans<<'\n';
    }
}

Information

Submit By
Type
Submission
Problem
P1156 Low cost water management
Language
C++17 (G++ 13.2.0)
Submit At
2025-01-01 18:56:10
Judged At
2025-01-01 18:56:10
Judged By
Score
100
Total Time
176ms
Peak Memory
65.965 MiB