oj.uz

Submission #113105

# Submission time Handle Problem Language Result Execution time Memory
113105 2019-05-23T16:42:58 Z Bruteforceman Long Distance Coach (JOI17_coach) C++11
0 / 100
 2 ms 384 KB 
#include "bits/stdc++.h"
using namespace std;
long long s[200010];
long long d[200010];
long long c[200010];
int N, M;
long long X, W, T;
typedef pair <long long, int> pii;
vector <pii> v;

int pos[200010];
long long dp[200010];

int main(int argc, char const *argv[])
{
	scanf("%lld %d %d %lld %lld", &X, &N, &M, &W, &T);
	for(int i = 1; i <= N; i++) {
		scanf("%lld", &s[i]);
	}
	s[++N] = X;
	for(int i = 1; i <= N; i++) {
		v.push_back(pii(s[i] % T, i));
	}  
	for(int i = 1; i <= M; i++) {
		scanf("%lld %lld", &d[i], &c[i]);
		v.push_back(pii(d[i], -i));
	}
	sort(v.begin(), v.end());

	int now = 0;
	for(auto i : v) {	
		if(i.second > 0) {
			pos[i.second] = now;
		}
		++now;
	}
	long long ans = (X / T) + 1;
	for(int i = 1; i <= M; i++) {
		ans += 1 + ((X - d[i]) / T);
	}
	ans *= W;

	dp[0] = 0;
	for(int i = 1; i < v.size(); i++) {
		if(v[i].second < 0) {
			dp[i] = dp[i - 1];
		} else {
			long long var = s[v[i].second] / T;
			long long cost = 0;
			for(int cur = i; cur >= 0; cur--) {
				if(v[cur].second > 0 && v[cur].second < v[i].second) {
					break;
				}
				if(v[cur].second < 0) {
					int id = -v[cur].second;
					cost += c[id];
					cost -= W * (1 + ((X - d[id]) / T));
					cost += W * var;
				}
				if(cur > 0) {
					dp[i] = min(dp[i], dp[cur - 1] + cost);
				} else {
					dp[i] = min(dp[i], cost);
				}
			}
		}
	}
	ans += dp[v.size() - 1];
	printf("%lld\n", ans);
	return 0;
}

Compilation message

coach.cpp: In function 'int main(int, const char**)':
coach.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
coach.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %d %d %lld %lld", &X, &N, &M, &W, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &s[i]);
   ~~~~~^~~~~~~~~~~~~~~
coach.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &d[i], &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -