oj.uz

답안 #348965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348965 2021-01-16T08:03:48 Z shrek12357 Salesman (IOI09_salesman) C++14
19 / 100
 3000 ms 26440 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <iomanip>
#include <bitset>
//#include "network.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0);

const int MAXN = 1e5 + 5;

ll dp[MAXN];

int main() {
	//ifstream cin("bcount.in"); ofstream cout("bcount.out");
	ll n, u, d, s;
	cin >> n >> u >> d >> s;
	vector<pair<ll, pair<ll, ll>>> nums;
	for (int i = 0; i < n; i++) {
		ll t, l, x;
		cin >> t >> l >> x;
		nums.push_back({ t, {l, x} });
	}
	nums.push_back({ 0, {s, 0} });
	nums.push_back({ 1e12, {s, 0} });
	sort(nums.begin(), nums.end());
	for (int i = 0; i < nums.size(); i++) {
		dp[i] = -1e12;
	}
	dp[0] = 0;
	for (int i = 0; i < nums.size(); i++) {
		for (int j = 0; j < i; j++) {
			if (nums[j].second.first > nums[i].second.first) {
				dp[i] = max(dp[i], dp[j] + nums[i].second.second - (nums[j].second.first - nums[i].second.first) * u);
			}
			else {
				dp[i] = max(dp[i], dp[j] + nums[i].second.second - (nums[i].second.first - nums[j].second.first) * d);
			}
		}
	}
	/*int ans = 0;
	for (int i = 0; i < n; i++) {
		if (nums[i].second.first > s) {
			ans = max(ans, dp[i] - (nums[i].second.first - s) * u);
		}
		else {
			ans = max(ans, dp[i] - (s - nums[i].second.first) * d);
		}
	}*/
	cout << dp[nums.size()  - 1] << endl;
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = 0; i < nums.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
salesman.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < nums.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
19.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 10 ms 492 KB Output is correct
5 Correct 55 ms 684 KB Output is correct
6 Correct 860 ms 1256 KB Output is correct
7 Execution timed out 3078 ms 2148 KB Time limit exceeded
8 Execution timed out 3076 ms 3552 KB Time limit exceeded
9 Runtime error 147 ms 9552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 294 ms 16704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 318 ms 16992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 384 ms 21584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 402 ms 21628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 525 ms 26304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 500 ms 26296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 495 ms 26352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Correct 1 ms 364 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct
19 Incorrect 3 ms 364 KB Output isn't correct
20 Incorrect 15 ms 492 KB Output isn't correct
21 Incorrect 15 ms 492 KB Output isn't correct
22 Incorrect 54 ms 620 KB Output isn't correct
23 Incorrect 52 ms 620 KB Output isn't correct
24 Incorrect 54 ms 684 KB Output isn't correct
25 Execution timed out 3063 ms 3552 KB Time limit exceeded
26 Runtime error 201 ms 12112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 323 ms 19136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 349 ms 19136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 467 ms 26440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 490 ms 26176 KB Execution killed with signal 11 (could be triggered by violating memory limits)