oj.uz

Submission #176097

# Submission time Handle Problem Language Result Execution time Memory
176097 2020-01-07T22:28:13 Z mat_v Boxes with souvenirs (IOI15_boxes) C++14
0 / 100
 2 ms 380 KB 
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#include "boxes.h"
#define maxn 10000005
using namespace std;
typedef long long ll;
int n,k;
int niz[maxn];
int d;
set<int>s;
ll dist(int l, int r){
    if(l > r)swap(l, r);
    ll res = min(r - l, l + d - r);
    return res;
}

ll levi[maxn];
ll desni[maxn];
long long delivery(int N, int K, int L, int p[]) {
    n = N, k = K, d = L;
    ff(i,1,n)niz[i] = p[i - 1];
    ff(i,1,n){
        s.insert(niz[i]);
    }
    n = s.size();
    int br = 1;
    for(auto c:s){
        niz[br++] = c;
    }
    levi[0] = 0;
    desni[n + 1] = 0;
    ff(i,1,n){
        if(k == 1 || i%k == 1){
            levi[i] = levi[i - 1] + 2*niz[i];
        }
        else{
            levi[i] = levi[i - 1] - niz[i - 1] + niz[i] - niz[i - 1] + niz[i];
        }
    }
    fb(i,n,1){
        int kol = n - i + 1;
        if(kol%k == 1 || k == 1){
            desni[i] = desni[i + 1] + 2*(d-niz[i]);
            //cout << i << " " << desni[i] << endl;
            //exit(0);
        }
        else{
            desni[i] = desni[i + 1] - (d-niz[i + 1]) + (d-niz[i]) - (d-niz[i + 1]) + (d-niz[i]);
        }
    }
    ll res = levi[1] + desni[2];
    ff(i,1,n){
        res = min(res, levi[i] + desni[i + 1]);
    }
    ff(i,1,n){
        res = min(res, levi[i - 1] + d + desni[i + k]);
    }
    return res;
}
/*
int aa[105];
int N,K,L;
int main(){
    cin >> N >> K >> L;
    ff(i,0,N - 1)cin >> aa[i];
    cout << delivery(N,K,L,aa);
    return 0;
}
/*
3 2 8
1 2 5
*/

Compilation message

boxes.cpp:70:1: warning: "/*" within comment [-Wcomment]
 /*
  
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:26:15: warning: conversion to 'int' from 'std::set<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     n = s.size();
         ~~~~~~^~

Subtask #1
0 / 10.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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