제출 #60828

#제출 시각아이디문제언어결과실행 시간메모리
60828dukati8선물상자 (IOI15_boxes)C++14
20 / 100
2 ms432 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a; i<int(b); i++) #define all(x) x.begin(),x.end() long long delivery(int N, int K, int L, int p[]) { if (K==1) { long long tot=0; rep(i,0,N) { tot+=2*min(p[i],L-p[i]); } return tot; } map<long long,int> places; long long biggestplace=0; rep(i,0,N) { long long curr=p[i]; biggestplace=max(biggestplace,curr); if (places.find(curr)!=places.begin()) places[curr]++; else places[curr]=1; } map<int,long long> dpthing; //This dp should be, for every possible amount of boxes that chould have been transported //to all the teams before and including the place we are at, minimum time to get there with those boxes dpthing.insert(make_pair(0,0)); long long prevplace=0; long long extratime=0; int need=0; for (auto a:places) { long long loc=a.first; int amount=a.second; extratime+=(amount/K)*8*min(loc,L-loc); amount%=K; if (amount==0) continue; long long mintime=1000000000000000; need+=amount; vector<int> rem; for (auto b:dpthing) { int have=b.first; mintime=min(mintime,b.second); if (have>=need) break; rem.push_back(have); } for (auto b:rem) { dpthing.erase(b); } //Now everything in dpthing has enough for this new location, they move there and increase time by the distance extratime+=min(loc-prevplace,L-loc+prevplace); //We can also go back and fetch new boxes, this should be added to the previous smallest mintime mintime+=min(prevplace,L-prevplace) + min(loc,L-loc); //Time to go back and fetch more and go to new place mintime-=min(loc-prevplace,L-loc+prevplace); //This was added to extratime instead dpthing.insert(make_pair(need-amount+K,mintime)); //We would have need-amount+K after that prevplace=loc; } //Now we take the least value in dpthing, add time to get back and extratime to it long long best=1000000000000000; for (auto a:dpthing) { best=min(best,a.second); } return best + min(biggestplace,L-biggestplace) + extratime; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...