oj.uz

Submission #27876

# Submission time Handle Problem Language Result Execution time Memory
27876 2017-07-14T10:20:24 Z khsoo01 Sparklers (JOI17_sparklers) C++11
0 / 100
 0 ms 2804 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 100005, inf = 1e11;
ll n, k, t, a[N], gp;

vector<ll> fw, bw;

void conv (vector<ll> &A, vector<pll> &B) {
	if(A.empty()) return;
	vector<ll> tmp;
	for(ll i=0,S=0;i<A.size();i++) {
		S += A[i];
		if(i+1 == A.size() || (A[i] >= 0) != (A[i+1] >= 0)) {
			tmp.push_back(S); S = 0;
		}
	}
	if(tmp[0] >= 0) gp += tmp[0];
	for(ll i=(tmp[0] >= 0);i<tmp.size();) {
		ll P = tmp[i], C = tmp[i]; i++;
		while(i<tmp.size() && P < 0) {
			P += tmp[i]; C = min(C, P); i++;
		}
		B.push_back(pll(C, P));
	}
}

bool can (ll X) {
	vector<ll> tf, tb;
	vector<pll> cf, cb;
	for(auto &T : fw) tf.push_back(2*t*X-T);
	for(auto &T : bw) tb.push_back(2*t*X-T);
	gp = 0;
	conv(tf, cf); conv(tb, cb);
	for(ll i=0,j=0;i<cf.size()||j<cb.size();) {
		bool flag = false;
		if(i == cf.size()) {
			if(gp + cb[j].X >= 0) flag = 1;
			else return false;
		}
		else if(j == cb.size()) {
			if(gp + cf[i].X >= 0) flag = 0;
			else return false;
		}
		else if(gp+cf[i].X >= 0 && cf[i].Y >= 0) flag = 0;
		else if(gp+cb[j].X >= 0 && cb[j].Y >= 0) flag = 1;
		else if(cf[i].X < cb[j].X && gp + cf[i].X >= 0) flag = 0;
		else if(gp + cb[j].X >= 0) flag = 1;
		else return false;
		if(flag) {gp += cb[j].Y; j++;}
		else {gp += cf[i].Y; i++;}
	}
	return true;
}

int main()
{
	scanf("%lld%lld%lld",&n,&k,&t);
	bool f = false;
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		if(a[i] != a[i-1]) f = true;
	}
	if(!f) {puts("0"); return 0;}
	for(ll i=k-1;i>=1;i--) fw.push_back(a[i+1]-a[i]);
	for(ll i=k+1;i<=n;i++) bw.push_back(a[i]-a[i-1]);
	ll S = 1, E = (inf+t-1)/t;
	while(S < E) {
		ll M = (S+E)/2;
		can(M) ? E = M : S = M+1;
	}
	printf("%lld\n",S);
}

Compilation message

sparklers.cpp: In function 'void conv(std::vector<long long int>&, std::vector<std::pair<long long int, long long int> >&)':
sparklers.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0,S=0;i<A.size();i++) {
                  ^
sparklers.cpp:17:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1 == A.size() || (A[i] >= 0) != (A[i+1] >= 0)) {
          ^
sparklers.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=(tmp[0] >= 0);i<tmp.size();) {
                          ^
sparklers.cpp:24:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i<tmp.size() && P < 0) {
          ^
sparklers.cpp: In function 'bool can(ll)':
sparklers.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0,j=0;i<cf.size()||j<cb.size();) {
                  ^
sparklers.cpp:38:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0,j=0;i<cf.size()||j<cb.size();) {
                               ^
sparklers.cpp:40:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == cf.size()) {
        ^
sparklers.cpp:44:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(j == cb.size()) {
             ^
sparklers.cpp: In function 'int main()':
sparklers.cpp:61:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&k,&t);
                                ^
sparklers.cpp:64:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct
5 Correct 0 ms 2804 KB Output is correct
6 Correct 0 ms 2804 KB Output is correct
7 Correct 0 ms 2804 KB Output is correct
8 Correct 0 ms 2804 KB Output is correct
9 Correct 0 ms 2804 KB Output is correct
10 Correct 0 ms 2804 KB Output is correct
11 Correct 0 ms 2804 KB Output is correct
12 Incorrect 0 ms 2804 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct
5 Correct 0 ms 2804 KB Output is correct
6 Correct 0 ms 2804 KB Output is correct
7 Correct 0 ms 2804 KB Output is correct
8 Correct 0 ms 2804 KB Output is correct
9 Correct 0 ms 2804 KB Output is correct
10 Correct 0 ms 2804 KB Output is correct
11 Correct 0 ms 2804 KB Output is correct
12 Incorrect 0 ms 2804 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct
5 Correct 0 ms 2804 KB Output is correct
6 Correct 0 ms 2804 KB Output is correct
7 Correct 0 ms 2804 KB Output is correct
8 Correct 0 ms 2804 KB Output is correct
9 Correct 0 ms 2804 KB Output is correct
10 Correct 0 ms 2804 KB Output is correct
11 Correct 0 ms 2804 KB Output is correct
12 Incorrect 0 ms 2804 KB Output isn't correct
13 Halted 0 ms 0 KB -