제출 #28761

#제출 시각아이디문제언어결과실행 시간메모리
28761repeating선물상자 (IOI15_boxes)C++11
0 / 100
6 ms376 KiB
#include <bits/stdc++.h> #include "boxes.h" #define F first #define S second #define P push #define pb push_back #define MEM(dp,i) memset(dp,i,sizeof(dp)) #define W while #define R return #define C continue #define SI size() #define ll long long #define ld long double #define pll pair<ll,ll> #define pii pair<int,int> #define SF(x) scanf("%I64d",&x) #define SF2(x,y) scanf("%I64d%I64d",&x,&y) #define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z) #define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o) #define all(v) v.begin(),v.end() using namespace std; const long long INF = 1e8; const int MX=1000015; int n,k,l; pii a[MX]; ll DP(vector<pii> &v){ int s=0,m=v.SI; for(int i=0;i<m;i++){ s+=v[i].S; } ll ret=0; int i=0; int h=s%k; if(h==0)h=k; W(i<m){ if(v[i].S>h){ ret+=v[i].F*2; h=k-v[i].S+h; ret+=v[i+1].F-v[i].F; i++; C; } if(v[i].S<h){ h-=v[i].S; ret+=v[i+1].F-v[i].F; i++; C; } if(v[i].S==h){ h=k; if(i==m-1)ret+=v[i].F; else{ ret+=v[i].F*2; ret+=v[i+1].F-v[i].F; } i++; } } if(v.SI) ret+=v[0].F; // cout<<ret<<" "; // for(int i=0;i<v.SI;i++) // cout<<v[i].F<<','<<v[i].S<<" "; // cout<<endl; R ret; } ll bs(int mid){ vector<pii> v1,v2; ll ret=0; int s1=0,s2=0; for(int i=0;i<mid;i++){ v1.pb(a[i]); s1+=a[i].S; } for(int i=n-1;i>=mid;i--){ v2.pb({l-a[i].F,a[i].S}); s2+=a[i].S; } ret=DP(v1)+DP(v2); if(!v1.empty()&&v1.back().S>s1%k&&s1%k){ v1[v1.SI].S-=s1%k; v2.pb({l-v1.back().F,s1%k}); ret=min(ret,DP(v1)+DP(v2)); v1[v1.SI].S+=s1%k; v2.pop_back(); } if(!v2.empty()&&v2.back().S>s2%k&&s2%k){ v2[v2.SI].S-=s2%k; v1.pb({l-v2.back().F,s2%k}); ret=min(ret,DP(v1)+DP(v2)); v2[v2.SI].S+=s2%k; v1.pop_back(); } R ret; } long long delivery(int N, int K, int L, int p[]) { n=N,k=K,l=L; sort(p,p+n); int j=0; for(int i=0;i<n;j++,i++){ a[j].F=p[i]; a[j].S=1; W(i<n-1&&p[i]==p[i+1]) a[j].S++,i++; } n=j; ll ret; for(int i=0;i<n;i++) ret=min(ret,bs(i)); // bs(1); return ret; }

컴파일 시 표준 에러 (stderr) 메시지

boxes.cpp: In function 'long long int DP(std::vector<std::pair<int, int> >&)':
boxes.cpp:11:16: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
 #define SI size()
                ^
boxes.cpp:28:17: note: in expansion of macro 'SI'
     int s=0,m=v.SI;
                 ^~
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:112:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ret;
            ^~~
#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...