Timus-1119 Metro

Problem NameMetro
JudgeTimus
Problem Linkhttps://acm.timus.ru/problem.aspx?space=1&num=1119
Algorithms & DSDynamic Programming
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define PB push_back
#define VST(V) sort(V.begin(),V.end())
#define VSTrev(V) sort(V.begin(),V.end(),greater<long long int>())
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
bitset<1010>ck[1010];
ll dp[1010][1010];
int main()
{
    //freopen("1input.txt","r",stdin);
    fast;
    ll tcase=1;
    //cin>>tcase;
    for(ll test=1; test<=tcase; test++)
    {
        ll n,m;
        cin>>n>>m;
        for(ll i=0; i<=n; i++)
        {
            for(ll j=0; j<=m; j++)
            {
                dp[i][j]=0;
                ck[i][j]=0;
            }
        }
        ll k;
        cin>>k;
        for(ll i=0; i<k; i++)
        {
            ll a,b;
            cin>>a>>b;
            ck[a][b]=1;
        }
        for(ll i=0; i<=n; i++)
        {
            for(ll j=0; j<=m; j++)
            {
                if(ck[i][j]==1)
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
                }
                if(i-1>=0)
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j]);
                }
                if(j-1>=0)
                {
                    dp[i][j]=max(dp[i][j],dp[i][j-1]);
                }
            }
        }
        ll cnt=dp[n][m];
        ll lagbe=n+m;
        double ans=lagbe-(cnt*2);
        ans*=100;
        double diagonal=(141.4213562*cnt);
        ans+=diagonal;
        ll res=round(ans);
        cout<<res<<"\n";
    }
    return 0;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
error: Alert: Content is protected !!