Submission #432205

#	Time	Username	Problem	Language	Result	Execution time	Memory
432205		jeqcho	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	1 ms	332 KiB

boxes

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;

#define FOR(i,a,b) for(int i=a;i<b;++i)
#define F0R(i,b) FOR(i,0,b)
#define ROF(i,a,b) for(int i=b-1;i>=a;--i)
#define R0F(i,b) ROF(i,0,b)
#define trav(a,x) for(auto&a:x)
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define pb push_back
#define sz(x) int(x.size())

int const N=1e3+3;
vpi adj[N];
int n;
bitset<N>vis;
ll d[N];
ll const INF=1e18;

ll delivery(int n1, int K, int L, int p[]) {
    n=n1;
    F0R(i,n)
    {
        int w;
        if(i==n-1)
        {
            w=L-p[i];
        }
        else
        {
            w=p[i+1]-p[i];
        }
        adj[i].pb({i+1,w});
        adj[i+1].pb({i,w});
    }
    adj[n].pb({0,p[0]});
    priority_queue<pair<ll,int>>q;
    q.push({0,n});
    d[n]=0;
    fill(d,d+n,INF);
    while(!q.empty())
    {
        int u=q.top().se;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        trav(e,adj[u])
        {
            int w=d[u]+e.se;
            if(w<d[e.fi])
            {
                d[e.fi]=w;
                q.push({-w,e.fi});
            }
        }
    }
    ll ans=0;
    F0R(i,n)
    {
        ans+=d[i];
    }
    return ans*2;
}

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:58:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   58 |             int w=d[u]+e.se;
      |                       ^
boxes.cpp:29:25: warning: unused parameter 'K' [-Wunused-parameter]
   29 | ll delivery(int n1, int K, int L, int p[]) {
      |                     ~~~~^

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