oj.uz

Submission #163602

# Submission time Handle Problem Language Result Execution time Memory
163602 2019-11-14T09:48:09 Z Knps4422 Boxes with souvenirs (IOI15_boxes) C++14
0 / 100
 2 ms 380 KB 
#include <bits/stdc++.h>
#include "boxes.h"
#define ll long long 
#define fr first
#define sc second
#define pb push_back
using namespace std;

ll n, k, L1;
ll pos[1000005];
ll cl[1000005], ct[1000005];
ll mid_of_circle;
void find1(){
	int l = 1 , r = n;
	int mid = (l+r)/2;
	while(l < r){
		mid = (l+r)/2; 
		if(pos[mid] >= L1/2){
			r = mid;
		}else{
			l = mid+1;
		}
	}
	// l is the first position after the middle of the circle
	mid_of_circle = l;
}
ll delivery(int N,int K,int L,int p[]){
	n = N;
	L1 = L;
	k = K;
	for(int i = 1; i <= n ; i++){
		pos[i] = p[i-1];
	}
	// cl[i] - result if we take only the first i positions
	for(ll i = 1; i <= n ; i++){
		cl[i] = cl[max((ll)0,i-k)] + 2*pos[i];
	}
	// ct[i] - result if we take only the last positions from i to n
	for(ll i = n; i > 0 ; i--){
		ct[i] = ct[min(n+1,i+k)] + 2*(L - pos[i]);
	}
	find1();
	ll rez = 1e18+7;
	for(ll i = 0 ; i < mid_of_circle ; i++){
		ll new_rez; 
		for(ll j = 0; i + k*j <= n ; j++){
			if(i + k*j + 1 >= mid_of_circle){
				new_rez = cl[i] + j*L + ct[i + k*j + 1];
				rez = min(rez,new_rez);
			}
		}
	}
	return rez;
}

Compilation message

boxes.cpp: In function 'void find1()':
boxes.cpp:14:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  int l = 1 , r = n;
                  ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -