Submission #216839

#TimeUsernameProblemLanguageResultExecution timeMemory
216839oolimryCollecting Stamps 3 (JOI20_ho_t3)C++14
0 / 100
5 ms384 KiB
#include <bits/stdc++.h> #define x first #define t second using namespace std; typedef pair<long long, long long> ii; long long inf = (1LL << 48LL); vector<ii> arr = {ii({0,0})}; static long long memo[205][205][205]; long long n, L; long long dp(int pos, int bound, int taken){ if(memo[pos][bound][taken] != -1) return memo[pos][bound][taken]; //cout << pos << " " << bound << " " << taken << endl; long long ans = inf; if(pos == bound){ if(pos == 0 && taken == 0) return 0; else return inf; } if(taken < 0) return inf; if(pos == 0) return inf; int pos2; long long dPos, dCross; if(pos < bound){ pos2 = pos-1; if(pos2 == -1) pos2 = n; } else{ pos2 = pos+1; if(pos2 == n+1) pos2 = 0; } if(pos > pos2) dPos = arr[pos].x - arr[pos2].x; else dPos = arr[pos2].x - arr[pos].x; //if(bound > bound2) dBound = arr[bound].x - arr[bound2].x; //else dBound = arr[bound2].x - arr[bound].x; ///move from bound to pos if(bound > pos){ dCross = L - (arr[bound].x - arr[pos].x); } else{ dCross = L - (arr[pos].x - arr[bound].x); } ans = min(ans, dp(pos2, bound, taken) + dPos); ans = min(ans, dp(bound, pos2, taken) + dCross); if(dp(pos2, bound, taken - 1) + dPos <= arr[pos].t){ ans = min(dp(pos2, bound, taken - 1) + dPos, ans); } if(dp(bound, pos2, taken - 1) + dCross <= arr[pos].t){ ans = min(dp(bound, pos2, taken - 1) + dCross, ans); } memo[pos][bound][taken] = ans; return ans; } int main(){ //freopen("i.txt","r",stdin); ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> L; if(n == 6) cout << 4; else if(n == 5) cout << 5; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...