oj.uz

Submission #106373

# Submission time Handle Problem Language Result Execution time Memory
106373 2019-04-18T04:11:49 Z jwvg0425 코알라 (JOI13_koala) C++17
20 / 100
 2000 ms 4320 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <iterator>
#include <chrono>
#define MOD 1000000007
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

i64 table[100005];
i64 d, a;
i64 b[100005];
i64 pos[100005];
bool memoed[100005];

i64 solve(int idx)
{
	if (idx == 0)
		return 0;

	if (memoed[idx])
		return table[idx];

	memoed[idx] = true;

	auto& res = table[idx];

	res = b[idx] - (pos[idx]  - pos[0] + d - 1) / d * a;

	for (int i = 1; i < idx; i++)
		res = max(res, solve(i) + b[idx] - (pos[idx] - pos[i] + d - 1) / d * a);

	return res;
}

int main()
{
	i64 k, m, n;
	scanf("%lld %lld %lld %lld %lld", &k, &m, &d, &a, &n);

	pos[0] = k;
	pos[n + 1] = m;

	for (int i = 1; i <= n; i++)
		scanf("%lld %lld", &pos[i], &b[i]);

	printf("%lld\n", solve(n + 1));

	return 0;
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld %lld", &k, &m, &d, &a, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &pos[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 12 ms 384 KB Output is correct
3 Correct 10 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 13 ms 384 KB Output is correct
6 Correct 9 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 10 ms 384 KB Output is correct
9 Correct 11 ms 384 KB Output is correct
10 Correct 9 ms 384 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 4196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 4320 KB Time limit exceeded
2 Halted 0 ms 0 KB -