# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
216748 | 2020-03-28T02:30:10 Z | LittleFlowers__ | 선물상자 (IOI15_boxes) | C++14 | 2000 ms | 71296 KB |
#include <bits/stdc++.h> using namespace std; #define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;}) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r){return l+rng()%(r-l+1);} #define fasty ios_base::sync_with_stdio(0),cin.tie(0); #define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a) #define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a) #define forv(a,b) for(auto&a:b) #define fi first #define se second #define pb push_back #define ii pair<int,int> #define mt make_tuple #define all(a) a.begin(),a.end() #define reset(f, x) memset(f, x, sizeof(f)) #define bit(x,i) ((x>>(i-1))&1) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1<<(i-1))) #define gg exit(0); //#define unx 1 #ifndef unx #include "boxes.h" #endif // unx const int N=3010; int n,k,m; int a[N],lf[N],rt[N]; long long f[N][N]; vector<int> val={0}; long long dfs(int l,int r){ if(l-1<=r) return 0; long long &ret=f[l][r] ; if(ret>-1) return ret; ret=LLONG_MAX; long long sum; forinc(i,r+1,l-1){ sum=lf[i]-lf[l]; ret=min(ret,dfs(i,r) + (sum ? ((sum-1)/k+1)*(m-val[i])*2 : 0)); sum=rt[i]-rt[r]; ret=min(ret,dfs(l,i) + (sum ? ((sum-1)/k+1)*val[i]*2 : 0)); } return ret; } long long delivery(int N,int K,int L,int p[]){ n=N, k=K, m=L; reset(f,-1); forinc(i,0,n-1) val.push_back(p[i]); sort(all(val)), val.erase(unique(all(val)),val.end()); forinc(i,0,n-1) a[(int)(lower_bound(all(val),p[i])-val.begin())]++; a[0]=0; L=val.size(); forinc(i,0,L-1) rt[i]=rt[i-1]+a[i]; fordec(i,L-1,0) lf[i]=lf[i+1]+a[i]; return dfs(L,0); } #ifdef unx main(){ #define task "boxes" freopen(task".inp","r",stdin); //freopen(task".out","w",stdout); int n,k,l; cin>>n>>k>>l; int p[1010]; forinc(i,1,n) cin>>p[i-1]; cout<<delivery(n,k,l,p)<<"\n"; } #endif // unx
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 71288 KB | Output is correct |
2 | Execution timed out | 2092 ms | 71296 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 613 ms | 71288 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 43 ms | 71288 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 71288 KB | Output is correct |
2 | Execution timed out | 2092 ms | 71296 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 71288 KB | Output is correct |
2 | Execution timed out | 2092 ms | 71296 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 71288 KB | Output is correct |
2 | Execution timed out | 2092 ms | 71296 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |