Submission #262101

#	Time	Username	Problem	Language	Result	Execution time	Memory
262101		patrikpavic2	Cake 3 (JOI19_cake3)	C++17	24 / 100	145 ms	73828 KiB

cake3

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef long long ll;

const int N = 2e3 + 50;
const ll INF = 1e18;

ll dp[N][N];
int C[N], V[N], n, m;
vector < pii > v;

ll f(int i, int j){
	if(j > i) return -INF;
	if(dp[i][j] != -1) return dp[i][j];
	if(j == 1)
		return dp[i][j] = max(f(i - 1, 1) + 2LL * (C[i - 1] - C[i]), (ll)V[i]);
	return dp[i][j] = max(f(i - 1, j), f(i - 1, j - 1) + V[i]) + 2LL * (C[i - 1] - C[i]);
}

int main(){
	memset(dp, -1, sizeof(dp));	
	scanf("%d%d", &n, &m);
	for(int i = 0;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v.PB({y, x});
	}
	sort(v.begin(), v.end());
	for(int i = 0;i < n;i++)
		C[i + 1] = v[i].X, V[i + 1] = v[i].Y;
	ll sol = -INF;
	for(int i = m;i <= n;i++){
		//printf("ubacujem %d %d\n", C[i], V[i]);
		//printf("dp : ");
		//for(int j = 1;j <= n && j <= i;j++)
		//	printf("%lld ", f(i, j));
		//printf("\ndel : ");
		//for(int j = 1;j <= n && j <= i;j++)
		//	printf("%lld ", f(i, j) - f(i, j - 1));
		//printf("\n");
		sol = max(sol, f(i, m));
	}
	printf("%lld\n", sol);
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
cake3.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 0 / 76