Submission #727919

#	Time	Username	Problem	Language	Result	Execution time	Memory
727919		atarii	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	1 ms	340 KiB

boxes

#include<bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define ll long long
#define foru(i, a, b, k) for(int i = a; i <= b; i+=k)
#define umap unordered_map
#define pii pair<int, int>
#define ford(i, a, b, k) for(int i = a; i >= b; i-=k)
#define vint vector<int>
#define vll vector<long long>
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
#define pb push_back
#define sz(s) (int)s.size()
#define ctn continue
#define ld long double

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
template<typename T> ll power(T a, const T b) { ll res = 1, x = a, y = b; while(y){if(y & 1)res *= x; x = x * x; y>>=1;}; return res; }
template<typename T> ll modpower(T a, T b, const T &m) { ll res = 1, x = a, y = b; x %= m; while(y){if(y & 1){res *= x; res %= m;}; x = x * x; x %= m; y >>= 1; } return res % m; }
template<typename T> T __lcm(T &a, T &b) { return a / __gcd(a, b) * b; }

template <typename T> bool getbit(T val, int i) { return (val >> i) & 1; }
template <typename T> int cntbit(T val)        { return val == 0 ? 0 : cntbit(val >> 1) + (val & 1); }
template <typename T> T offbit(T val, int i) { return val & (~(T(1) << i)); }
template <typename T> T onbit(T val, int i) { return val | (T(1) << i); }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const  ll  MOD = 998244353;
const  ll  LIM = 9e5;
const int    N = 2e5 + 5;
const int  INF = 0x3f3f3f3f;
const  ll LINF = 2e18;
const int maxL = 7;
const int base = 3e5 + 1;
const string File = "test";

vector <int> a;
ll pre[N], suf[N];

ll delivery(int n, int k, int l, int p[])
{
    a.pb(0);
    foru(i, 1, n, 1) if(p[i])
        a.pb(p[i]);

    sort(all(a));

    n = sz(a) - 1;

    // pre[i]: chi phí tối thiểu để đi đến i, có full quà trong túi
    foru(i, 1, n, 1)
    {
        if(i < k)
        {
            pre[i] = min({a[i] * 2, l - a[i] + a[i], (l - a[i]) * 2});
        }
        else pre[i] = pre[i - k + 1] + (a[i] - a[i - k + 1]) + min({a[i], l - a[i] + a[i], (l - a[i])});
    }

    ford(i, n, 1, 1)
    {
        if(i + k - 1 > n)
        {
            suf[i] = min({a[i] * 2, l - a[i] + a[i], (l - a[i]) * 2});
        }
        else suf[i] = suf[i + k - 1] + (a[i + k - 1] - a[i]) + min({a[i], l - a[i] + a[i], (l - a[i])});
    }

    ll res = pre[n];
    foru(i, 1, n, 1) minimize(res, pre[i - 1] + suf[i]);

    return res;
}

Compilation message (stderr)

boxes.cpp: In function 'int readInt()':
boxes.cpp:31:51: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   31 | inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
      |                                            ~~~~~~~^~
boxes.cpp:31:114: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   31 | inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
      |                                                                                                           ~~~~~~~^~
boxes.cpp:31:144: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   31 | inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
      |                                                                                                                                         ~~~~~~~^~
boxes.cpp: In function 'long long int readLong()':
boxes.cpp:32:51: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   32 | inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
      |                                            ~~~~~~~^~
boxes.cpp:32:114: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   32 | inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
      |                                                                                                           ~~~~~~~^~
boxes.cpp:32:144: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   32 | inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
      |                                                                                                                                         ~~~~~~~^~
boxes.cpp: In function 'std::string readString()':
boxes.cpp:33:51: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   33 | inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
      |                                            ~~~~~~~^~
boxes.cpp:33:109: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   33 | inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
      |                                                                                                      ~~~~~~~^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30