Submission #35595592

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _(i,n) for (ll i=0;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

ll dp[2010][2010][2][2];
const ll INF=0x3f3f3f3f3f3f3f3f;
ll r[2010];
ll c[2010];

int a[2010][2010];
char s[2010];
void setMin(ll&a,ll b){a=min(a,b);}

int main(){
  int h=read();
  int w=read();
  _(i,h)r[i]=read();
  _(j,w)c[j]=read();
  _(i,h){
    scanf("%s",s);
    _(j,w)a[i][j]=s[j]-'0';
  }
  _(i,h)_(j,w)_(x,2)_(y,2)dp[i][j][x][y]=INF;
  _(x,2)_(y,2)dp[0][0][x][y]=x*r[0]+y*c[0];
  _(i,h)_(j,w)_(x,2)_(y,2){
    ll cost=dp[i][j][x][y];
    if(cost==INF)continue;
    int color=a[i][j]^x^y;
    if(i+1<h){
      int rev=color^a[i+1][j]^y;
      setMin(dp[i+1][j][rev][y],cost+rev*r[i+1]);
    }
    if(j+1<w){
      int rev=color^a[i][j+1]^x;
      setMin(dp[i][j+1][x][rev],cost+rev*c[j+1]);
    }
  }
  ll ans=INF;
  _(x,2)_(y,2)setMin(ans,dp[h-1][w-1][x][y]);
  printf("%lld\n",ans);
  return 0;
}

Submission Info

Submission Time
Task F - Monochromatic Path
User cromarmot
Language C++ (GCC 9.2.1)
Score 500
Code Size 964 Byte
Status AC
Exec Time 161 ms
Memory 145176 KiB

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:5:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    5 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:22:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%s",s);
      |     ~~~~~^~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 45
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 6 ms 3824 KiB
001.txt AC 2 ms 3824 KiB
002.txt AC 154 ms 145148 KiB
003.txt AC 155 ms 145040 KiB
004.txt AC 159 ms 145144 KiB
005.txt AC 161 ms 145096 KiB
006.txt AC 153 ms 145052 KiB
007.txt AC 153 ms 145176 KiB
008.txt AC 155 ms 144956 KiB
009.txt AC 154 ms 144944 KiB
010.txt AC 153 ms 145060 KiB
011.txt AC 154 ms 145164 KiB
012.txt AC 152 ms 145064 KiB
013.txt AC 33 ms 27300 KiB
014.txt AC 50 ms 44392 KiB
015.txt AC 53 ms 47208 KiB
016.txt AC 118 ms 115220 KiB
017.txt AC 13 ms 10336 KiB
018.txt AC 51 ms 44972 KiB
019.txt AC 85 ms 78512 KiB
020.txt AC 61 ms 55536 KiB
021.txt AC 33 ms 28016 KiB
022.txt AC 36 ms 28992 KiB
023.txt AC 154 ms 144916 KiB
024.txt AC 152 ms 144948 KiB
025.txt AC 153 ms 145164 KiB
026.txt AC 154 ms 145048 KiB
027.txt AC 153 ms 144908 KiB
028.txt AC 152 ms 144908 KiB
029.txt AC 152 ms 145064 KiB
030.txt AC 153 ms 145064 KiB
031.txt AC 155 ms 145056 KiB
032.txt AC 153 ms 145052 KiB
033.txt AC 154 ms 144956 KiB
034.txt AC 151 ms 145144 KiB
035.txt AC 151 ms 144920 KiB
036.txt AC 150 ms 145092 KiB
037.txt AC 155 ms 145044 KiB
038.txt AC 152 ms 145124 KiB
039.txt AC 154 ms 144908 KiB
040.txt AC 152 ms 145020 KiB
041.txt AC 153 ms 145020 KiB
042.txt AC 151 ms 145044 KiB
example0.txt AC 3 ms 3684 KiB
example1.txt AC 2 ms 3828 KiB