oj.uz

Submission #118952

# Submission time Handle Problem Language Result Execution time Memory
118952 2019-06-20T05:55:44 Z oolimry Boxes with souvenirs (IOI15_boxes) C++14
100 / 100
 627 ms 277148 KB 
#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;

static long long leftl[10000005];
static long long rightr[10000005];
static long long pp[10000005];
long long delivery(int N, int K, int L, int p[]) {
    long long n, k, l;
    n = N, k = K, l = L;

    for(int i = 0;i < n;i++){
        pp[i] = p[i];
    }
    for(int i = 0;i < n;i++){
        if(i < k) leftl[i] = 2ll * pp[i];
        else leftl[i] = 2ll * pp[i] + leftl[i-k];
    }

    for(int i = n-1;i >= 0;i--){
        if(i + k >= n) rightr[i] = 2ll * l - 2ll * pp[i];
        else rightr[i] = 2ll * l - 2ll * pp[i] + rightr[i+k];
    }

    //for(int i = 0;i < n;i++){
    //    cout << leftl[i] << " " << rightr[i] << "\n";
    //}

    long long circles = n / k + 2;
    long long ans = min(leftl[n-1], rightr[0]);
    for(int i = -1;i < n;i++){
        long long value = 0;
        if(i != -1) value += leftl[i];

        while(true){
            if(circles == 0) break;

            int pnt2 = i + 1 + k * (circles - 1);
            if(pnt2 >= n){
                circles--;
            }
            else if(L >= 2 * L - 2 * pp[pnt2]){
                circles--;
            }
            else{
                break;
            }
        }

        value += circles * l;
        int endpnt = i + 1 + k * circles;
        if(endpnt < n) value += rightr[endpnt];
        //cout << i << " " << circles << "\n";
        ans = min(ans,value);
    }
    return ans;
}

Compilation message

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:20:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     for(int i = n-1;i >= 0;i--){
                 ~^~
boxes.cpp:38:30: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             int pnt2 = i + 1 + k * (circles - 1);
                        ~~~~~~^~~~~~~~~~~~~~~~~~~
boxes.cpp:51:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         int endpnt = i + 1 + k * circles;
                      ~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 432 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 356 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 356 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 380 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 432 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 356 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 356 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 380 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 58 ms 27700 KB Output is correct
34 Correct 34 ms 29688 KB Output is correct
35 Correct 38 ms 30200 KB Output is correct
36 Correct 57 ms 37564 KB Output is correct
37 Correct 58 ms 37552 KB Output is correct
38 Correct 64 ms 37500 KB Output is correct
39 Correct 58 ms 36032 KB Output is correct
40 Correct 40 ms 31308 KB Output is correct
41 Correct 58 ms 37624 KB Output is correct
42 Correct 38 ms 31608 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 432 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 356 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 356 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 380 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 58 ms 27700 KB Output is correct
34 Correct 34 ms 29688 KB Output is correct
35 Correct 38 ms 30200 KB Output is correct
36 Correct 57 ms 37564 KB Output is correct
37 Correct 58 ms 37552 KB Output is correct
38 Correct 64 ms 37500 KB Output is correct
39 Correct 58 ms 36032 KB Output is correct
40 Correct 40 ms 31308 KB Output is correct
41 Correct 58 ms 37624 KB Output is correct
42 Correct 38 ms 31608 KB Output is correct
43 Correct 579 ms 277148 KB Output is correct
44 Correct 325 ms 274936 KB Output is correct
45 Correct 352 ms 274808 KB Output is correct
46 Correct 627 ms 277124 KB Output is correct
47 Correct 577 ms 277100 KB Output is correct
48 Correct 578 ms 277120 KB Output is correct
49 Correct 537 ms 276548 KB Output is correct
50 Correct 392 ms 275540 KB Output is correct
51 Correct 580 ms 277064 KB Output is correct
52 Correct 382 ms 275320 KB Output is correct