oj.uz

Submission #572077

# Submission time Handle Problem Language Result Execution time Memory
572077 2022-06-03T13:46:47 Z nohaxjustsoflo Boxes with souvenirs (IOI15_boxes) C++17
100 / 100
 654 ms 333040 KB 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen(-1e9, 1e8); ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 1e6+50000;
const int mod = 1e9+7;
const int mxlogN = 34;
const int mxK = 26;
const ll inf = 1e18;
const int K = 100000;

ll delivery(int N, int K, int L, int p[])
{
    ll n=N, k=K;
    ll cnt=0;
    if(n%2==0) for(int i=0; i<n; i++) cnt+=p[i]==n/2;
    ll ans=cnt/k*n;
    cnt=cnt%k;
    vector<int> a;
    for(int i=0; i<n; i++)
    {
        if(n%2==0&&p[i]==n/2)
        {
            if(cnt)
            {
                cnt--;
                a.push_back(p[i]);
            }
        }
        else a.push_back(p[i]);
    }
    n=a.size();
    vector<ll> pre(n), suf(n);
    for(int i=0; i<n; i++)
    {
        if(i>=k) pre[i]+=pre[i-k];
        pre[i]+=a[i]*2;
        //cout << pre[i] << " ";
    }
    //cout << "\n";
    for(int i=n-1; i>=0; i--)
    {
        if(i+k<n) suf[i]+=suf[i+k];
        suf[i]+=(L-a[i])*2;
        //cout << suf[i] << " ";
    }
    //cout << "\n";
    ll ans2=1e18;
    for(int j=0; j<3; j++)
    {
        for(int i=0; i+j*K<=n; i++)
        {
            //pre[i-1]+suf[i];
            ans2=min(ans2,L*j+(i?pre[i-1]:0)+(i+j*K<n?suf[i+j*K]:0));
        }
    }
    return ans+ans2;
}

/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,k,l; cin >> n >> k >> l;
    int p[n];
    for(int i=0; i<n; i++) cin >> p[i];
    cout << delivery(n,k,l,p) << "\n";

}*/
/*
3 2 8
1 2 5
*/

Compilation message

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:21:24: warning: declaration of 'K' shadows a global declaration [-Wshadow]
   21 | ll delivery(int N, int K, int L, int p[])
      |                    ~~~~^
boxes.cpp:19:11: note: shadowed declaration is here
   19 | const int K = 100000;
      |           ^
boxes.cpp:50:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |     for(int i=n-1; i>=0; i--)
      |               ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 304 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 316 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 320 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 312 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 304 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 316 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 320 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 312 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 62 ms 33472 KB Output is correct
34 Correct 32 ms 25840 KB Output is correct
35 Correct 31 ms 26340 KB Output is correct
36 Correct 60 ms 33564 KB Output is correct
37 Correct 61 ms 33560 KB Output is correct
38 Correct 59 ms 33716 KB Output is correct
39 Correct 53 ms 32052 KB Output is correct
40 Correct 34 ms 27524 KB Output is correct
41 Correct 59 ms 33688 KB Output is correct
42 Correct 38 ms 27812 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 304 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 316 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 320 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 312 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 62 ms 33472 KB Output is correct
34 Correct 32 ms 25840 KB Output is correct
35 Correct 31 ms 26340 KB Output is correct
36 Correct 60 ms 33564 KB Output is correct
37 Correct 61 ms 33560 KB Output is correct
38 Correct 59 ms 33716 KB Output is correct
39 Correct 53 ms 32052 KB Output is correct
40 Correct 34 ms 27524 KB Output is correct
41 Correct 59 ms 33688 KB Output is correct
42 Correct 38 ms 27812 KB Output is correct
43 Correct 654 ms 331768 KB Output is correct
44 Correct 312 ms 254808 KB Output is correct
45 Correct 343 ms 262576 KB Output is correct
46 Correct 624 ms 333008 KB Output is correct
47 Correct 629 ms 332844 KB Output is correct
48 Correct 617 ms 333040 KB Output is correct
49 Correct 608 ms 317852 KB Output is correct
50 Correct 383 ms 271692 KB Output is correct
51 Correct 631 ms 332980 KB Output is correct
52 Correct 384 ms 274336 KB Output is correct