oj.uz

답안 #369399

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
369399 2021-02-21T14:32:56 Z AmineWeslati Salesman (IOI09_salesman) C++14
0 / 100
 26 ms 11884 KB 
//Never stop trying
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
#define int ll
typedef string str;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 800 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}
#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////

int N,L,R,S;
vi T(MX),X(MX),V(MX),vec,pos(MX);

bool cmp(int i, int j){
	return X[i]<X[j];
}

int cost(int i, int j){
	if(X[i]<X[j]) return (X[j]-X[i])*R;
	return (X[i]-X[j])*L;
}
	
int memo[MX][MX];
int solve(int l, int r){
	int i=l; if(T[r]>T[l]) i=r;

	int &ind=memo[l][r];
	if(ind!=-1) return ind;

	int ans=-cost(i,0);
	
	int j=pos[r]+1;
	if(j<N && T[vec[j]]>T[i]){
		ckmax(ans,solve(l,vec[j])+V[vec[j]]-cost(i,vec[j]));
	}
	
	int jj=j;
	j=pos[l]-1;

	if(j>=0 && T[vec[j]]>T[i]){
		ckmax(ans,solve(vec[j],r)+V[vec[j]]-cost(i,vec[j]));
	}

	return ind=ans;
}

int32_t main() {
    boost; IO();

    cin>>N>>L>>R>>S;
    FOR(i,1,N+1) cin>>T[i]>>X[i]>>V[i];
    N++;
    T[0]=-INF; X[0]=S; V[0]=0;
    
    vec.resize(N);
    iota(all(vec),0);
    sort(all(vec),cmp);
    dbgv(vec)

    FOR(i,0,N) pos[vec[i]]=i;

    memset(memo,-1,sizeof(memo));
    cout << solve(0,0) << endl;


    return 0;
}
//Change your approach

Compilation message

salesman.cpp: In function 'll solve(ll, ll)':
salesman.cpp:81:6: warning: unused variable 'jj' [-Wunused-variable]
   81 |  int jj=j;
      |      ^~

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5484 KB Output isn't correct
2 Incorrect 3 ms 5484 KB Output isn't correct
3 Incorrect 3 ms 5484 KB Output isn't correct
4 Runtime error 11 ms 10988 KB Execution killed with signal 11
5 Runtime error 13 ms 11116 KB Execution killed with signal 11
6 Runtime error 17 ms 11884 KB Execution killed with signal 11
7 Runtime error 7 ms 1516 KB Execution killed with signal 11
8 Runtime error 10 ms 2284 KB Execution killed with signal 11
9 Runtime error 10 ms 3052 KB Execution killed with signal 11
10 Runtime error 17 ms 5484 KB Execution killed with signal 11
11 Runtime error 17 ms 5484 KB Execution killed with signal 11
12 Runtime error 21 ms 7020 KB Execution killed with signal 11
13 Runtime error 21 ms 7020 KB Execution killed with signal 11
14 Runtime error 26 ms 8568 KB Execution killed with signal 11
15 Runtime error 25 ms 8684 KB Execution killed with signal 11
16 Runtime error 25 ms 8684 KB Execution killed with signal 11
17 Incorrect 3 ms 5484 KB Output isn't correct
18 Incorrect 4 ms 5484 KB Output isn't correct
19 Runtime error 15 ms 10988 KB Execution killed with signal 6
20 Runtime error 11 ms 11072 KB Execution killed with signal 11
21 Runtime error 11 ms 10988 KB Execution killed with signal 11
22 Runtime error 12 ms 11116 KB Execution killed with signal 11
23 Runtime error 12 ms 11264 KB Execution killed with signal 11
24 Runtime error 12 ms 11116 KB Execution killed with signal 11
25 Runtime error 8 ms 2284 KB Execution killed with signal 11
26 Runtime error 12 ms 3820 KB Execution killed with signal 11
27 Runtime error 19 ms 6252 KB Execution killed with signal 11
28 Runtime error 19 ms 6400 KB Execution killed with signal 11
29 Runtime error 26 ms 8812 KB Execution killed with signal 11
30 Runtime error 25 ms 8812 KB Execution killed with signal 11