oj.uz

Submission #114163

# Submission time Handle Problem Language Result Execution time Memory
114163 2019-05-31T04:12:09 Z jwvg0425 코알라 (JOI13_koala) C++17
30 / 100
 2000 ms 3920 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 d, a;
i64 b[100005];
i64 pos[100005];

bool work[105];
i64 cost[105];
i64 last[105];

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]);

	cost[k%d] = 0;
	work[k%d] = true;
	last[k%d] = k;

	for (int i = 1; i <= n + 1; i++)
	{
		bool isFirst = true;
		i64 nowCost = 0;
		i64 nowLast = 0;

		for (int di = 0; di < d; di++)
		{
			if (!work[di])
				continue;

			i64 c = cost[di] + b[i];

			c -= (pos[i] - last[di] + d - 1) / d * a;

			if (isFirst || c > nowCost)
			{
				nowCost = c;
				nowLast = pos[i];
				isFirst = false;
			}
		}
		cost[pos[i] % d] = nowCost;
		last[pos[i] % d] = nowLast;
		work[pos[i] % d] = true;
	}

	printf("%lld\n", cost[pos[n + 1] % d]);

	return 0;
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:41: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:47: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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3832 KB Output is correct
2 Correct 146 ms 3704 KB Output is correct
3 Correct 22 ms 2560 KB Output is correct
4 Correct 89 ms 3920 KB Output is correct
5 Correct 45 ms 2432 KB Output is correct
6 Correct 32 ms 1536 KB Output is correct
7 Correct 35 ms 2824 KB Output is correct

Subtask #3
0 / 50.0

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