oj.uz

Submission #79392

# Submission time Handle Problem Language Result Execution time Memory
79392 2018-10-13T03:41:10 Z Plurm Boxes with souvenirs (IOI15_boxes) C++11
0 / 100
 5 ms 376 KB 
#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;

long long delivery(int N, int K, int L, int p[]) {
	vector<int> a,b;
	for(int i = 0; i < N; i++){
		if(p[i] < L-p[i]){
			a.push_back(p[i]);
		}else{
			b.push_back(L-p[i]);
		}
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	vector<long long> dpa,dpb;
	dpa.resize(a.size());
	if(!a.empty())
		dpa[0] = 2ll*a[0];
	long long mn = (long long)(N+K-1)/(long long)K*(long long)L;
	for(int i = 1; i < a.size(); i++){
		mn = min(mn,dpa[i-1] + (long long)(N-i+K-1)/(long long)K*(long long)L);
		dpa[i] = i >= K ? dpa[i-K] : 0ll;
		dpa[i] += 2ll*(long long)a[i];
	}
	if(!a.empty()){
		mn = min(mn,dpa[a.size()-1] + (long long)(N+a.size()+K-2)/(long long)K*(long long)L);
	}
	dpb.resize(b.size());
	if(!b.empty())
		dpb[0] = 2ll*b[0];
	for(int i = 1; i < b.size(); i++){
		mn = min(mn,dpb[i-1] + (long long)(N-i+K-1)/(long long)K*(long long)L);
		for(int j = 0; j < a.size(); j++){
			mn = min(mn,dpa[j] + dpb[i-1] + (long long)(N-i-j+K-2)/(long long)K*(long long)L);
		}
		dpb[i] = i >= K ? dpb[i-K] : 0ll;
		dpb[i] += 2ll*(long long)b[i];
	}
	if(!b.empty()){
		mn = min(mn,dpb[b.size()-1] + (long long)(N-b.size()+K-2)/(long long)K*(long long)L);
		for(int j = 0; j < a.size(); j++){
			mn = min(mn,dpa[j] + dpb[b.size()-1] + (long long)(N-b.size()-j+K-2)/(long long)K*(long long)L);
		}
	}
	return mn;
}

Compilation message

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < a.size(); i++){
                 ~~^~~~~~~~~~
boxes.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < b.size(); i++){
                 ~~^~~~~~~~~~
boxes.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < a.size(); j++){
                  ~~^~~~~~~~~~
boxes.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < a.size(); j++){
                  ~~^~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 376 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 256 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 256 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 256 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 256 KB Output isn't correct
2 Halted 0 ms 0 KB -