oj.uz

답안 #98220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98220 2019-02-21T15:20:39 Z SuperJava Salesman (IOI09_salesman) C++17
15 / 100
 263 ms 21624 KB 
//fold
#ifndef KHALIL
#include <bits/stdc++.h>
#else
#include "header.h"
#endif
#define endl '\n'
#define mp make_pair
#define tostr(x) static_cast<ostringstream&>((ostringstream()<<dec<<x)).str()
#define rep(i,begin,end) for(auto i = begin;i < end;i++)
#define repr(i,begin,end) for(auto i = begin-1;i >= end;i--)
#define pb push_back
#define sz(a) ((int)(a).size())
#define fi first
#define se second
#define abs(a) ((a) < (0) ? (-1)*(a) : (a))
#define SQ(a) ((a)*(a))
#define eqd(a,b) (abs(a-b)<1e-9)
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename t> t in(t q){cin >> q;return q;}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v){os << "[";for (int i = 0; i < sz(v); ++i) { os << v[i]; if (i != sz(v) - 1) os << ",";}os << "]";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const map<T, S>& v){for (auto it : v)os << "(" << it.first << ":" << it.second << ")";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const pair<T, S>& v){os << "(" << v.first << "," << v.second << ")";return os;}
const long double PI = acosl(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng);}
//endfold
#define  N  (5005)
#define MOD (1000000000l + 7l)
#define OO (1050000000)
#define OOL (1100000000000000000)

struct fair{
	int day,loc,mon;
};

vector<fair> a;
// i, l
int dp[2][N];

int main(){
	//fold
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cout << setprecision(10);
	//endfold
	int n,u,d,s;
	cin >> n >> u >> d >> s;
	for (int i = 0; i < n; ++i){
		int t,l,m;
		cin >> t >> l >> m;
		a.push_back({t,l,m});
	}
	sort(a.begin(), a.end(),[](fair a,fair b){
		return a.day < b.day;
	});
	for (int i = 1; i < s; ++i){
		dp[1][i] = -(s-i)*d;
	}
	for (int i = s+1; i < 5001; ++i){
		dp[1][i] = -(i-s)*u;
	}
	for (int i = n-1; i >= 0; --i){
		for (int l = 1; l < 5001; ++l){
			int dist = 0;
			if(l < a[i].loc) dist = (a[i].loc-l)*d;
			else dist = (l-a[i].loc)*u;
			dp[0][l] = max(dp[1][l],a[i].mon+dp[1][a[i].loc]-dist);
		}
		for (int l = 1; l < 5001; ++l){
			dp[1][l] = dp[0][l];
		}
	}
	cout << dp[0][s];
	return 0;
}

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 10 ms 384 KB Output is correct
4 Correct 32 ms 512 KB Output is correct
5 Correct 70 ms 632 KB Output is correct
6 Runtime error 15 ms 1768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 35 ms 2928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 67 ms 4972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 67 ms 6628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 150 ms 12576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 179 ms 13216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 212 ms 16364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 208 ms 16764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 243 ms 21624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 263 ms 20816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 219 ms 20692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 3 ms 384 KB Output isn't correct
18 Incorrect 8 ms 384 KB Output isn't correct
19 Incorrect 15 ms 384 KB Output isn't correct
20 Incorrect 39 ms 512 KB Output isn't correct
21 Incorrect 36 ms 512 KB Output isn't correct
22 Incorrect 75 ms 640 KB Output isn't correct
23 Incorrect 67 ms 732 KB Output isn't correct
24 Incorrect 59 ms 640 KB Output isn't correct
25 Runtime error 36 ms 4584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 80 ms 8416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 127 ms 13692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 164 ms 14520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 174 ms 19160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 199 ms 20112 KB Execution killed with signal 11 (could be triggered by violating memory limits)