QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#474578#366. Long Distance Coachltunjic0 0ms1660kbC++201.1kb2024-07-12 20:28:172024-07-12 20:28:17

Judging History

你现在查看的是最新测评结果

  • [2024-07-12 20:28:17]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:1660kb
  • [2024-07-12 20:28:17]
  • 提交

answer

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

using namespace std; 

typedef long long ll; 

const int N = 2010;

int n, m;
ll s[N], d[N], c[N], t, w;
int fst[N], ind[N]; // -1
			
ll dp[N];

int main() { 
	ll X;
	scanf("%lld%d%d%lld%lld", &X, &n, &m, &w, &t);
	s[n + 1] = X;
	for(int i = 1; i <= n; ++i) { scanf("%lld", s + i); }

	ll sum = (X / t + 1LL) * w;
	for(int i = 0; i < m; ++i) { 
		scanf("%lld%lld", d + i, c + i); 
		sum += c[i];
		ind[i] = i;
	}

	sort(ind, ind + m, [](ll a, ll b) { 
		return d[a] < d[b];
	});
	sort(s, s + n + 2, [](ll a, ll b) { 
		return a < b;
	});

	memset(fst, -1, sizeof(fst));
	for(int j = m - 1; j >= 0; --j) { 
		int x = ind[j];
		dp[j] = dp[j + 1] - c[x] + ((X - d[x]) / t + 1LL) * w;
		for(int i = 1; i <= n + 1; ++i) { 
			ll k = (s[i] - d[x]) / t;
			if(d[x] + k * t > s[i - 1] && (k + 1LL) * t > s[i]) { 
				if(fst[i] == -1) { fst[i] = j; }
				dp[j] = min(dp[j], dp[fst[i] + 1] + (ll) k * w * (ll) (fst[i] - j + 1));
			}
		}
	}
	
	printf("%lld\n", sum + dp[0]);
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1660kb

input:

999999999999 1 1 1000000 4
1
2 3

output:

250000000000000003

result:

wrong answer 1st lines differ - expected: '499999999999000003', found: '250000000000000003'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%