Submission #173984

#	Time	Username	Problem	Language	Result	Execution time	Memory
173984		FieryPhoenix	Boxes with souvenirs (IOI15_boxes)	C++11	100 / 100	1780 ms	300808 KiB

boxes

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include "boxes.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001001001
#define MOD 1000000007

struct MinQ{
  stack<pair<ll,ll>>s1,s2;
  int size(){
    return (int)s1.size()+(int)s2.size();
  }
  void insert(ll x){
    ll mn=x;
    if (!s1.empty())
      mn=min(mn,s1.top().second);
    s1.push({x,mn});
  }
  void pop(){
    assert((int)s1.size()+(int)s2.size()>0);
    if (s2.size()==0){
      while (s1.size()>0){
	ll mn=s1.top().first;
	if (!s2.empty())
	  mn=min(mn,s2.top().second);
	s2.push({s1.top().first,mn});
	s1.pop();
      }
    }
    s2.pop();
  }
  ll query(){
    assert((int)s1.size()+(int)s2.size()>0);
    ll mn=INF;
    if (s1.size()>0) mn=min(mn,s1.top().second);
    if (s2.size()>0) mn=min(mn,s2.top().second);
    return mn;
  }
};

ll dpL[10000001],dpR[10000001];

ll delivery(int N, int K, int L, int pos[]){
  MinQ q;
  //from left side
  q.insert(0);
  for (int i=0;i<N;i++){
    if (q.size()>K)
      q.pop();
    dpL[i]=q.query()+pos[i]+min(pos[i],L-pos[i]);
    q.insert(dpL[i]);
  }
  while (q.size())
    q.pop();
  //from right side;
  q.insert(0);
  for (int i=N-1;i>=0;i--){
    if (q.size()>K)
      q.pop();
    dpR[i]=q.query()+L-pos[i]+min(pos[i],L-pos[i]);
     q.insert(dpR[i]);
  }
  ll ans=INF;
  for (int i=0;i+1<N;i++){
    if (i+1<N)
      ans=min(ans,dpL[i]+dpR[i+1]);
  }
  ans=min(ans,dpL[N-1]);
  ans=min(ans,dpR[0]);
  return ans;
}

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