Timus-1119 Metro

T
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; }
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!