Submission #673797

#TimeUsernameProblemLanguageResultExecution timeMemory
673797sudheerays123Lightning Rod (NOI18_lightningrod)C++17
40 / 100
2051 ms262144 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ll long long int const ll N = 100+5 , INF = 1e18 , MOD = 1e9+7; bool inside(ll x1 , ll y1 , ll x2 , ll y2){ return (abs(x2-x1) <= (y2-y1)); } void solve(){ ll n; cin >> n; vector<pair<ll,ll>> a(n+5); for(ll i = 1; i <= n; i++) cin >> a[i].first >> a[i].second; vector<ll> left(n+5); for(ll i = 1; i <= n; i++){ ll last = INF; for(ll j = i+1; j <= n; j++){ if(!inside(a[j].first,a[j].second,a[i].first,a[i].second)){ last = j-1; break; } } if(last == INF) last = n; left[i] = last; } vector<ll> dp(n+5); dp[1] = 1; for(ll i = 1; i <= n; i++){ dp[i] = dp[i-1]+1; bool allinside = true; for(ll j = i-1; j >= 1; j--){ if(left[j] >= i){ dp[i] = min(dp[i],dp[j]); } if(inside(a[j].first,a[j].second,a[i].first,a[i].second) && allinside){ dp[i] = min(dp[i],dp[j-1]+1); } else allinside = false; } } cout << dp[n]; } int main(){ fast; ll tc = 1; // cin >> tc; while(tc--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...