oj.uz

Submission #140489

# Submission time Handle Problem Language Result Execution time Memory
140489 2019-08-03T08:39:02 Z bazsi700 Shortcut (IOI16_shortcut) C++14
0 / 100
 2 ms 380 KB 
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL
#define hashA 1257958787
#define hashB 1539500609
#define endl "\n"

ll pref[10005];
vector<int> l;
vector<int> d;
int n,c;

ll getdist(ll a, ll b) {
	if(a > b) {
		swap(a,b);
	}
	return pref[b]-pref[a];
}

ll getcost(int b1, int b2) {
	ll mx = 0;
	ll worstnormal = d[0];
	ll worstshort = d[0]+getdist(0,b1);
	for(int v = 1; v < n; v++) {
		worstnormal+= l[v-1];
		ll dist = worstnormal+d[v];
		dist = min(dist,worstshort+c+getdist(v,b2)+d[v]);
		worstshort = max(worstshort,getdist(v,b1)+d[v]);
		worstnormal = max(worstnormal,(ll)d[v]);
		mx = max(mx,dist);
	}
	return mx;
}

ll find_shortcut(int N, vector<int> L, vector<int> D, int C) {
	n = N;
	c = C;
	l = L;
	d = D;
	ll ans = 0;
	ll currdist = d[0];
	for(int i = 1; i < n; i++) {
		pref[i] = pref[i-1]+l[i-1];
	}/*
	for(int i = 1; i < n; i++) {
		currdist+= l[i-1];
		ans = max(ans,currdist+d[i]);
		currdist = max(currdist,(ll)d[i]);
	}*/
	ll mn = INF;
	for(int b1 = 0; b1 < n; b1++) {
		int b2l = b1+1;
		int b2r = n-1;
		ll best = INF;
		while(b2l < b2r) {
			int b2 = (b2l+b2r)/2;
			ll val1 = getcost(b1,b2);
			ll val2 = getcost(b1,b2+1);
			if(val2 > val1) {
				b2r = b2;
			} else {
				b2l = b2+1;
			}
			best = min(best,val1);
			best = min(best,val2);
		}
		best = min(best,getcost(b1,b2l));
		best = min(best,getcost(b1,b2r));
	}
	return mn;
}

Compilation message

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:47:5: warning: unused variable 'ans' [-Wunused-variable]
  ll ans = 0;
     ^~~
shortcut.cpp:48:5: warning: unused variable 'currdist' [-Wunused-variable]
  ll currdist = d[0];
     ^~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB n = 4, incorrect answer: jury 80 vs contestant 9223372036854775807
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB n = 4, incorrect answer: jury 80 vs contestant 9223372036854775807
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB n = 4, incorrect answer: jury 80 vs contestant 9223372036854775807
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB n = 4, incorrect answer: jury 80 vs contestant 9223372036854775807
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB n = 4, incorrect answer: jury 80 vs contestant 9223372036854775807
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB n = 4, incorrect answer: jury 80 vs contestant 9223372036854775807
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB n = 4, incorrect answer: jury 80 vs contestant 9223372036854775807
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB n = 4, incorrect answer: jury 80 vs contestant 9223372036854775807
2 Halted 0 ms 0 KB -