Submission #238975

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238975	2020-06-13T20:48:38 Z	ant101	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	6 ms	384 KB

boxes

#include "boxes.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;

//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007

typedef long long ll;


ll add(ll a, ll b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
ll sub(ll a, ll b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}

ll mul(ll a, ll b) {
    return (a * b)%MOD;
}

void add_self(ll& a, ll b) {
    a = add(a, b);
}
void sub_self(ll& a, ll b) {
    a = sub(a, b);
}
void mul_self(ll& a, ll b) {
    a = mul(a, b);
}


const ll MAXN = 200010;

ll li[MAXN], ri[MAXN];

long long delivery(int N, int K, int L, int p[]) {
//    ios_base :: sync_with_stdio(false);
//    cin.tie(nullptr);
//    cin >> N >> K >> L;
//    for (ll i = 0; i<N; i++) {
//        cin >> p[i];
//    }
    ll zeroteams = 0;
    ll currdist = 0, remaining = K;
    for (ll i = 0; i<N; i++) {
        if (p[i] == 0) {
            zeroteams++;
            continue;
        }
        remaining--;
        currdist+=p[i]-(i == 0 ? 0 : p[i-1]);
        li[i-zeroteams+1] = currdist+p[i];
        if (remaining == 0) {
            remaining = K;
            currdist+=p[i]*2;
        }
    }
    currdist = 0;
    remaining = K;
    ll curr = 0;
    for (ll i = N-1; i>=0; i--) {
        if (p[i] == 0) {
            continue;
        }
        remaining--;
        curr++;
        currdist+=(i == N-1 ? L : p[i+1])-p[i];
        ri[curr] = currdist+p[i];
        if (remaining == 0) {
            remaining = K;
            currdist+=(L-p[i])*2;
        }
    }
    N-=zeroteams;
    ll best = 1e13;
    for (ll i = 0; i<=N; i++) {
        best = min(best, li[i]+ri[N-i]);
    }
    for (ll i = 0; i<=N; i++) {
        best = min(best, li[i]+L+ri[N-i-K]);
    }
    return best;
}


//int main() {
//    return 0;
//}
//

Compilation message

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:104:6: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     N-=zeroteams;
     ~^~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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