제출 #133215

#제출 시각아이디문제언어결과실행 시간메모리
133215KewoCake 3 (JOI19_cake3)C++17
0 / 100
11 ms9464 KiB
#include <bits/stdc++.h> #define pb push_back #define ppb pop_back #define fi first #define se second #define mid ((x + y) / 2) #define left (ind * 2) #define right (ind * 2 + 1) #define mp make_pair #define timer ((double)clock() / CLOCKS_PER_SEC) #define endl "\n" #define spc " " #define d1(x) cerr<<#x<<":"<<x<<endl #define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl #define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl #define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long int lli; typedef pair<lli, lli> ii; typedef pair<ii, int> iii; typedef pair<double, double> dd; const int N = (int)(1e2 + 5); const int LOG = (int)(20); const lli inf = (lli)(1e15); lli n, m, ans, dp[N][N][N]; ii p[N]; lli f(int x, int y, int z) { if(z < 0) return -inf; if(x == y + 1) { if(z == 0) return 0; else return -inf; } if(dp[x][y][z] != -1) return dp[x][y][z]; return dp[x][y][z] = max(f(x + 1, y, z), f(x + 1, y, z - 1) + p[x].se); } int main() { fast_io(); // freopen("inp.in", "r", stdin); memset(dp, -1, sizeof dp); cin >> n >> m; for(int i = 1; i <= n; i++) cin >> p[i].se >> p[i].fi; sort(p + 1, p + n + 1); for(int i = 1; i <= n; i++) for(int j = i + m - 1; j <= n; j++) ans = max(ans, f(i + 1, j - 1, m - 2) + p[i].se + p[j].se - 2 * (p[j].fi - p[i].fi)); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...