제출 #683950

#제출 시각아이디문제언어결과실행 시간메모리
683950pragmatist등산 경로 (IZhO12_route)C++17
0 / 100
2076 ms16096 KiB
/* #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("O3") #pragma GCC target ("avx2") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("unroll-loops") */ #include<bits/stdc++.h> #define ld long double #define sz(v) (int)v.size() #define ll long long #define pb push_back #define x first #define y second #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define nl "\n" using namespace std; using pii = pair<int, int>; const int N = (int)1e2 + 7; // make sure this is right const int M = (int)1e3 + 7; const int inf = (int)2e9 + 7; const ll INF = (ll)3e18 + 7; const double PI = acos(-1); ll MOD = (ll)1e9 + 7; // make sure this is right bool bit(int x, int i) { return x >> i & 1; } int sum(int x, int y) { x += y; if(x >= MOD) x -= MOD; return x; } pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int n, k, a[N], b[N]; ll dp[2][M][M]; void solve() { cin >> n >> k; int mx = 0; for(int i = 1; i <= n; ++i) { cin >> a[i]; if(a[i] > a[mx]) mx = i; } for(int i = mx; i <= n; ++i) b[i - mx + 1] = a[i]; for(int i = 1; i < mx; ++i) b[n - mx + 1 + i] = a[i]; for(int i = 1; i <= n; ++i) { a[i] = b[i]; } ll ans = INF, S = 0; for(int i = 0; i <= k; ++i) { for(int j = 0; j <= k; ++j) { dp[0][i][j] = dp[1][i][j] = INF; } } dp[0][0][0] = 0; for(int i = 2; i <= n; ++i) { for(int j = 0; j <= k; ++j) { for(int have = j; have <= k; ++have) { dp[1][j][have] = INF; for(int y = 0; have - j >= y; ++y) { dp[1][j][have] = min(dp[1][j][have], dp[0][y][have - j] + abs((a[i - 1] + y) - (a[i] + j))); } } } for(int j = 0; j <= k; ++j) { for(int have = 0; have <= k; ++have) { dp[0][j][have] = dp[1][j][have]; dp[1][j][have] = INF; } } } ll cur = INF; for(int i = 0; i <= k; ++i) { for(int j = 0; j <= k; ++j) { cur = min(cur, dp[0][i][j] + abs(a[1] - (a[n] + i))); } } S = dp[0][0][0] + abs(a[1] - a[n]); ans = min(ans, cur); cout << S - ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int test = 1; //cin >> test; for(int i = 1; i <= test; ++i) { //cout << "Case #" << i << ": "; solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...